bzoj3262陌上花开 三维数点 cdq+树状数组

大早上的做了一道三维数点一道五位数点，神清气爽！

先给一维排序，变成一个奇怪的动态的二维数点（相当于有一个扫描面扫过去，导致一系列的加点和询问）

然后cdq分治，再变回静态，考虑前半段对后半段的影响

这时对第二维排序，又变成动态一维数点

树状数组屠之

（不妨再cdq一次变成零维数点，也就是询问一个询问之前有几次修改）（手动滑稽）

另外因为x y z都相同时互相产生影响，特判掉

来上个又臭又长的代码

 #include <bits/stdc++.h>

 using namespace std;

 struct t

 {

     int x,y,z,num,ans;

 } a[],b[];

 int tr[],ans[];

 int n,m;

 bool comx(t a,t b)

 {

     return (a.x<b.x)||(a.x==b.x &&(a.y<b.y || (a.y==b.y &&a.z<b.z)));

 }

 bool same(t a,t b)

 {

     return (a.x==b.x && a.y==b.y && a.z==b.z);

 }

 void add(int x,int y)

 {

     while(x<=m)

         tr[x]+=y,x+=x&-x;

 }

 int que(int x)

 {

     int ans=;

     while(x)

         ans+=tr[x],x-=x&-x;

     return ans;

 }

 void cdq(int l,int r)

 {

     if(l==r)

         return;

     int mid=l+r>>;

     cdq(l,mid);cdq(mid+,r);

     for(int i=l,j=l,k=mid+;i<=r;i++)

         if(j<=mid &&(k>r || a[j].y<=a[k].y)) b[i]=a[j++];

             else b[i]=a[k++];

     for(int i=l;i<=r;i++)

     {

         a[i]=b[i];

         if(a[i].num<=mid)

             add(a[i].z,);

         else

             a[i].ans+=que(a[i].z);

     }

     for(int i=l;i<=r;i++)

     if(a[i].num<=mid)

         add(a[i].z,-);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

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

         scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);

     sort(a+,a+n+,comx);

     t tem;int te=;

     for(int i=n;i>=;i--)

         if(same(tem,a[i])) a[i].ans+=te,++te;

             else tem=a[i],te=;

 //    puts("");

 //    for(int i=1;i<=n;i++)

 //        printf("%d %d %d\n",a[i].x,a[i].y,a[i].z);

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

         a[i].num=i;

     cdq(,n);

 //    for(int i=1;i<=n;i++)

 //        printf("%d %d %d %d\n",a[i].x,a[i].y,a[i].z,a[i].ans);

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

         ++ans[a[i].ans];

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

         printf("%d\n",ans[i]);

     return ;

 }