CDQ分治模板
注意三元組完全相等的情況
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=100010,K=200010; 4 int n,k,cnt[N],ans[N]; 5 struct Node{ 6 int a,b,c,id; 7 bool operator<(const Node& k)const{ 8 if(b==k.b&&c==k.c) return a<=k.a; 9 if(b==k.b) return c<=k.c; 10 return b<=k.b; 11 } 12 }node[N],temp[N]; 13 int cmp(const Node& x,const Node& y){ 14 if(x.a==y.a&&x.b==y.b) return x.c<y.c; 15 if(x.a==y.a) return x.b<y.b; 16 return x.a<y.a; 17 } 18 inline int lowbit(int k){return k&(-k);} 19 int tree[K],vis[K],timer; 20 inline void add(int pos,int x){ 21 while(pos<=k){ 22 if(vis[pos]!=timer) vis[pos]=timer,tree[pos]=0; 23 tree[pos]+=x,pos+=lowbit(pos); 24 } 25 return; 26 } 27 inline int que(int pos){ 28 int res=0; 29 while(pos){ 30 if(vis[pos]!=timer) vis[pos]=timer,tree[pos]=0; 31 res+=tree[pos],pos-=lowbit(pos); 32 } 33 return res; 34 } 35 void cdq(int l,int r){ 36 if(l>=r) return; 37 int mid=(l+r)>>1; 38 cdq(l,mid);cdq(mid+1,r); 39 timer++; 40 int pi=l,pj=mid+1,x=l,pp; 41 while(pi<=mid&&pj<=r){ 42 if(node[pi]<node[pj]){ 43 add(node[pi].c,1); 44 temp[x++]=node[pi++]; 45 }else{ 46 ans[node[pj].id]+=que(node[pj].c); 47 pp=pi-1; 48 while(pp>=l&&node[pp].a==node[pj].a&&node[pp].b==node[pj].b&&node[pp].c==node[pj].c) ans[node[pp--].id]++; 49 temp[x++]=node[pj++]; 50 } 51 } 52 while(pi<=mid) temp[x++]=node[pi++]; 53 while(pj<=r){ 54 ans[node[pj].id]+=que(node[pj].c); 55 pp=mid; 56 while(pp>=l&&node[pp].a==node[pj].a&&node[pp].b==node[pj].b&&node[pp].c==node[pj].c) ans[node[pp--].id]++; 57 temp[x++]=node[pj++]; 58 } 59 for(int i=l;i<=r;i++) node[i]=temp[i]; 60 return; 61 } 62 int main(){ 63 int t1,t2,t3; 64 scanf("%d%d",&n,&k); 65 for(int i=1;i<=n;i++) scanf("%d%d%d",&t1,&t2,&t3),node[i]=(Node){t1,t2,t3,i}; 66 sort(node+1,node+n+1,cmp); 67 cdq(1,n); 68 for(int i=1;i<=n;i++) cnt[ans[i]]++; 69 for(int i=0;i<n;i++) printf("%d\n",cnt[i]); 70 return 0; 71 }
?
