打铁选手的 CDQ分治刷题记录

BZOJ3262

模板题，三位偏序。
注意第一维排完序之后再给二三维排序的时候还是要考虑下第一维的：如果二三维都相等的话第一维小的要在前面

代码：

 #include <bits/stdc++.h>

 #define nmax 1000100

 #define lowbit(x) x&(-x)

 using namespace std;

 struct point{

     int x,y,z;

     bool operator == (const point& c) const { return (c.x==x)&&(c.y==y)&&(c.z==z); }

 };

 point in[nmax],a[nmax];

 int n,k;

 int p[nmax],c[nmax]={},v[nmax]={},an[nmax]={},fa[nmax]={};

 bool cmp1(point c,point b){

     if(c.x==b.x) return (c.y==b.y)?(c.z<b.z):(c.y<b.y);

     else return c.x<b.x;

 }

 bool cmp2(int b,int c){

     if(a[b].y==a[c].y) return (a[b].z==a[c].z)?(a[b].x<a[c].x):(a[b].z<a[c].z);

     return a[b].y<a[c].y;  //第二次排序的时候也是要考虑a的

 }

 inline void addv(int x,int t){

     while(x<=k){ c[x]+=t; x+=lowbit(x); }

 }

 inline int f(int x){

     int ans=;

     while(x>) { ans+=c[x]; x-=lowbit(x); }

     return ans;

 }

 void solve(int l,int r){

     if(l==r) { an[l]+=(v[l]-); return; }

     int ans=,mid=(l+r)/;

     for (int i=l; i<=r; i++) p[i]=i;

     sort(p+l,p+r+,cmp2);

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

         int id=p[i];

         if(id<=mid) addv(a[id].z,v[id]); //在左边

         else {

                 an[id]+=f(a[id].z);   //在右边

  //               printf("now an[%d]=%d \n",id,an[id]);

         }

     }

     //清空树状数组

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

             int id=p[i];

             if(id<=mid) addv(a[id].z,(-)*v[id]);

     }

     solve(l,mid);

     solve(mid+,r);

 }

 int main(){

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

     for (int i=; i<=n; i++) scanf("%d%d%d",&in[i].x,&in[i].y,&in[i].z);

     sort(in+,in+n+,cmp1);

     //去重

     int cnt=,i=,j=;

     while (i<=n){

         a[++cnt]=in[i];

         v[cnt]=;

         while(in[i]==in[j]) { j++; v[cnt]++; }

         i=j; j++;

     }

     //去重 over 要处理的数组是a

     solve(,cnt);

     for (int i=; i<=cnt; i++) fa[an[i]]+=v[i];

     for (int i=; i<n; i++) printf("%d\n",fa[i]);

     return ;

 }

030

巴特西

打铁选手的 CDQ分治刷题记录

BZOJ3262

最新文章

热门文章

巴特西

打铁选手的 CDQ分治 刷题记录

BZOJ3262

最新文章

热门文章

打铁选手的 CDQ分治刷题记录