CF1045G AI robots（动态开点线段树）

题意

火星上有$N$个机器人排成一行，第$i$个机器人的位置为$x_{i}$，视野为$r_{i}$，智商为$q_{i}$。我们认为第$i$个机器人可以看到的位置是$[x_{i}-r_{i},x_{i}+r_{i}]$。如果一对机器人相互可以看到，且它们的智商$q_{i}$的差距不大于$K$，那么它们会开始聊天。 为了防止它们吵起来，请计算有多少对机器人可能会聊天。

题解

先膜一下大佬->这里

我们先按视野降序排序，这样一个一个考虑，如果后面的能看到前面，那前面的也肯定能看到后面

这样，就是对于每一个机器人，在他前面有几个智商在$[q-k,q+k]$，位置在$[x-r,x+r]$

那么把这个东西看做一个矩形覆盖就可以了

然后因为智商这一维维数很小，我们可以对每一个智商开一个动态开点线段树，然后一个一个扫过去统计答案就可以了

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<map>

 #define ll long long

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=1e5+;

 int n,k,m,b[N*];ll res;

 map<int,int> rt;int L[N<<],R[N<<],sum[N<<],cnt=;

 void update(int p,int l,int r,int x){

     ++sum[p];if(l==r) return;

     int mid=(l+r)>>;

     if(x<=mid) update(L[p]=L[p]?L[p]:++cnt,l,mid,x);

     else update(R[p]=R[p]?R[p]:++cnt,mid+,r,x);

 }

 int query(int p,int l,int r,int ql,int qr){

     if(ql<=l&&qr>=r||p==) return sum[p];

     int mid=(l+r)>>,res=;

     if(ql<=mid) res+=query(L[p],l,mid,ql,qr);

     if(qr>mid) res+=query(R[p],mid+,r,ql,qr);

     return res;

 }

 inline void ins(int q,int x){

     if(rt.count(q)==) rt[q]=++cnt;

     update(rt[q],,m,x);

 }

 inline int get(int q,int ql,int qr){

     if(rt.count(q)==) return ;

     return query(rt[q],,m,ql,qr);

 }

 struct node{

     int x,r,q;

     node(){}

     node(int x,int r,int q):x(x),r(r),q(q){}

     inline bool operator <(const node &b)const

     {return r>b.r;}

 }a[N];

 int main(){

 //    freopen("testdata.in","r",stdin);

     n=read(),k=read();

     for(int i=;i<=n;++i){

         int x=read(),r=read(),q=read();

         a[i]=node(x,r,q);

         b[++m]=x,b[++m]=x-r,b[++m]=x+r;

     }

     sort(b+,b++m),m=unique(b+,b++m)-b-;

     sort(a+,a++n);

     for(int i=;i<=n;++i){

         int l=lower_bound(b+,b++m,a[i].x-a[i].r)-b;

         int r=lower_bound(b+,b++m,a[i].x+a[i].r)-b;

         int x=lower_bound(b+,b++m,a[i].x)-b;

         for(int j=a[i].q-k;j<=a[i].q+k;++j)

         res+=get(j,l,r);

         ins(a[i].q,x);

     }

     printf("%lld\n",res);

     return ;

 }