蒟蒻不会什么CDQ分治，treap套树状数组写好。。。。。 看来还是有必要学一下cdq分治，逼近总不能每次拿着平衡树乱套啊！ 这道题大致思路就是排序、树状数组、treap，明了！！
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int maxn = 3000050; int size,n,k,p,val,x,y,z,ans,sum[maxn],tmp[maxn]; int root[maxn]; struct node{int x,y,z;}a[maxn]; int v[maxn],cnt[maxn],sz[maxn],ch[maxn][2],rnd[maxn]; inline int randlmy(){ static int seed=23; return seed=(int)seed*48271LL%2147483647; } bool cmp(node a,node b){ if(a.x==b.x&&a.y==b.y)return a.z<b.z; if(a.x==b.x)return a.y<b.y; return a.x<b.x; } void updata(int k){ sz[k]=sz[ch[k][0]]+sz[ch[k][1]]+cnt[k]; } void rotate(int &k,bool f){ int t=ch[k][f];ch[k][f]=ch[t][!f]; ch[t][!f]=k;updata(k);updata(t);k=t; } void insert(int &k){ if(!k){k=++size;rnd[k]=randlmy();v[k]=val;cnt[k]=sz[k]=1;return;} sz[k]++; if(v[k]==val){cnt[k]++;return;} bool f=val>v[k];insert(ch[k][f]); if(rnd[ch[k][f]]<rnd[k])rotate(k,f); } void rank(int k){ if(!k)return; if(v[k]==val)ans+=sz[ch[k][0]]; else if(v[k]>val)rank(ch[k][0]); else ans+=sz[ch[k][0]]+cnt[k],rank(ch[k][1]); } int low(int x){return x&(-x);} void update(int x,int p){ val=p;for(register int i=x;i<=k;i+=low(i))insert(root[i]); } void query(int x,int p){ val=p+1;for(register int i=x;i;i-=low(i))rank(root[i]); } template<class T>inline void read(T &res){ static char ch;T flag=1; while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48; while((ch=getchar())>='0'&&ch<='9')res=ch-48+res*10;res*=flag; } int main(){ read(n),read(k); for(register int i=1;i<=n;i++) read(a[i].x),read(a[i].y),read(a[i].z); sort(a+1,a+1+n,cmp); for(register int i=1;i<=n;i++){ if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z) sum[i+1]=sum[i]+1; else{ ans=0; query(a[i].y,a[i].z); tmp[ans]+=sum[i]+1; } update(a[i].y,a[i].z); } for(register int i=0;i<n;i++) printf("%d\n",tmp[i]); return 0; }