題意
火星上有$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]$
那么把這個東西看做一個矩形覆蓋就可以了
然后因為智商這一維維數很小，我們可以對每一個智商開一個動態開點線段樹，然后一個一個掃過去統計答案就可以了
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #include<map> 6 #define ll long long 7 using namespace std; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf; 10 inline int read(){ 11 #define num ch-'0' 12 char ch;bool flag=0;int res; 13 while(!isdigit(ch=getc())) 14 (ch=='-')&&(flag=true); 15 for(res=num;isdigit(ch=getc());res=res*10+num); 16 (flag)&&(res=-res); 17 #undef num 18 return res; 19 } 20 const int N=1e5+5; 21 int n,k,m,b[N*3];ll res; 22 map<int,int> rt;int L[N<<5],R[N<<5],sum[N<<5],cnt=0; 23 void update(int p,int l,int r,int x){ 24 ++sum[p];if(l==r) return; 25 int mid=(l+r)>>1; 26 if(x<=mid) update(L[p]=L[p]?L[p]:++cnt,l,mid,x); 27 else update(R[p]=R[p]?R[p]:++cnt,mid+1,r,x); 28 } 29 int query(int p,int l,int r,int ql,int qr){ 30 if(ql<=l&&qr>=r||p==0) return sum[p]; 31 int mid=(l+r)>>1,res=0; 32 if(ql<=mid) res+=query(L[p],l,mid,ql,qr); 33 if(qr>mid) res+=query(R[p],mid+1,r,ql,qr); 34 return res; 35 } 36 inline void ins(int q,int x){ 37 if(rt.count(q)==0) rt[q]=++cnt; 38 update(rt[q],1,m,x); 39 } 40 inline int get(int q,int ql,int qr){ 41 if(rt.count(q)==0) return 0; 42 return query(rt[q],1,m,ql,qr); 43 } 44 struct node{ 45 int x,r,q; 46 node(){} 47 node(int x,int r,int q):x(x),r(r),q(q){} 48 inline bool operator <(const node &b)const 49 {return r>b.r;} 50 }a[N]; 51 int main(){ 52 // freopen("testdata.in","r",stdin); 53 n=read(),k=read(); 54 for(int i=1;i<=n;++i){ 55 int x=read(),r=read(),q=read(); 56 a[i]=node(x,r,q); 57 b[++m]=x,b[++m]=x-r,b[++m]=x+r; 58 } 59 sort(b+1,b+1+m),m=unique(b+1,b+1+m)-b-1; 60 sort(a+1,a+1+n); 61 for(int i=1;i<=n;++i){ 62 int l=lower_bound(b+1,b+1+m,a[i].x-a[i].r)-b; 63 int r=lower_bound(b+1,b+1+m,a[i].x+a[i].r)-b; 64 int x=lower_bound(b+1,b+1+m,a[i].x)-b; 65 for(int j=a[i].q-k;j<=a[i].q+k;++j) 66 res+=get(j,l,r); 67 ins(a[i].q,x); 68 } 69 printf("%lld\n",res); 70 return 0; 71 }
?
實現的方法)
