题目大意：
火星上有 \(N\) 个机器人排成一行，第 \(i\) 个机器人的位置为 \(x_i\)，视野维 \(r_i\)，智商为 \(q_i\)。我们认为第 \(i\) 个机器人可以看到的位置是 \([x_i – r_i,x_i + r_i]\)。如果一对机器人可以相互看见，且他们的智商 \(q_i\) 的差距不大于 \(k\)，那么他们会开始聊天。为了防止他们炒起来，请计算有多少机器人可以聊天。
题目中出现了两个制约答案的条件：相互看见，智商差距小于 \(k\)。那么在一棵线段树种存储这两维的信息？显然是难以维护和查找的。考虑到颜色种类不多，我们可以对智商离散化，对每一种智商建一棵线段树，使我们能够查询某个区间内该智商的机器人总数。当然，我们还要对坐标进行离散化。注意，在离散化的过程中，除了将机器人的位置 \(r[i].x\) 加入离散化的动态数组，还要将 \(r[i].x + r[i].r\) 和 \(r[i].x – r[i].r\) 加入该动态数组，这样才能便于我们更好地确定每个机器人的视野内有多少个机器人。
除了记录答案的部分，大体思路如上。但这里有一个问题，如果我们按照传统线段树，开成\(tree[智商种类数][4 * MAXN]\) 这样的话空间显然会炸，那么就只能用动态开点线段树来解决。先确定最多会用到多少个结点。对于每个结点，记录其左儿子和右儿子的编号即可。像对于每一种智商开的新的线段树，用一个 \(root\) 数组记录它的根节点的编号，就可以实现动态开点了。
现在考虑最后一个问题：怎么统计答案？假如一个视野小的机器人能看见一个视野大的机器人，那么这对机器人肯定能够相互看见。然后枚举一个智商 \(j\)，使其与当前机器人的智商的差距不大于 \(k\)，将智商为 \(j\) 且在 \([x_i – r_i,x_i + r_i]\) 范围内的机器人的总数加起来，就是当前机器人能够吵架的机器人的总数。
#include<bits/stdc++.h>
#define mid (tl + tr) / 2
#define int long long
using namespace std;
int n,k;
const int N = 1e5 + 10;
const int MAXN = N * 10;
struct robot{
int x,r,q;
}r[MAXN + 25];
int root[MAXN + 25],tot;
struct node{
int ls,rs,num;
}tree[MAXN + 225];
vector<int> col;
int ans;
void change(int i,int tl,int tr,int pos){
if(tl == tr){
tree[i].num++;
return;
}
if(pos <= mid){
if(tree[i].ls == 0)tree[i].ls = ++tot;
change(tree[i].ls,tl,mid,pos);
}
else {
if(tree[i].rs == 0)tree[i].rs = ++tot;
change(tree[i].rs,mid + 1,tr,pos);
}
tree[i].num = tree[tree[i].ls].num + tree[tree[i].rs].num;
}
int query(int i,int tl,int tr,int l,int r){
if(tl > r || tr < l)return 0;
if(tl >= l && tr <= r)return tree[i].num;
int ss = 0;
if(tree[i].ls != 0)ss += query(tree[i].ls,tl,mid,l,r);
if(tree[i].rs != 0)ss += query(tree[i].rs,mid + 1,tr,l,r);
return ss;
}
bool cmp(robot a,robot b){
return a.r > b.r;
}
vector<int> pos;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
int mx = 0;
for(int i = 1; i <= n; i++){
cin >> r[i].x >> r[i].r >> r[i].q;
mx = max(mx,r[i].x);
col.push_back(r[i].q);
pos.push_back(r[i].x + r[i].r);
pos.push_back(r[i].x - r[i].r);
pos.push_back(r[i].x);
}
sort(col.begin(),col.end());
col.erase(unique(col.begin(),col.end()),col.end());
for(int i = 0; i < col.size(); i++){
root[i] = ++tot;
}
sort(pos.begin(),pos.end());
pos.erase(unique(pos.begin(),pos.end()),pos.end());
sort(r + 1,r + 1 + n,cmp);
for(int i = 1; i <= n; i++){
int now = lower_bound(col.begin(),col.end(),r[i].q) - col.begin();
int l = lower_bound(pos.begin(),pos.end(),r[i].x - r[i].r) - pos.begin() + 1;
int r1 = lower_bound(pos.begin(),pos.end(),r[i].x + r[i].r) - pos.begin() + 1;
int o = lower_bound(pos.begin(),pos.end(),r[i].x) - pos.begin() + 1;
for(int j = now + 1; j < col.size() && col[j] - r[i].q <= k; j++){
ans += query(root[j],1,pos.size(),l,r1);
}
for(int j = now; j >= 0 && r[i].q - col[j] <= k; j--){
ans += query(root[j],1,pos.size(),l,r1);
}
change(root[now],1,pos.size(),o);
}
cout << ans;
}
原文地址：http://www.cnblogs.com/CZ-9/p/16866482.html
