「BZOJ」「3262」陌上花开

CDQ分治

　　WA ：在solve时，对y、z排序以后，没有处理「y、z相同」的情况，也就是说可能（1，2，3）这个点被放到了（2，2，3）的后面，也就是统计答案在前，插入该点在后……也就没有统计到！

　　sad

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int N = ;

 int n,k;

 struct node{

     int x,y,z,id;

 }a[], b[];

 bool operator != (node a,node b){

     return a.x != b.x || a.y != b.y || a.z != b.z;

 }

 bool operator < (node a,node b){

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

 }

 bool cmp(node a,node b){

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

 }

 int ans[N], rank[N], num[N];

 int val[N], vis[N], times;

 inline int lowbit(int x){

     return x & (-x);

 }

 void add(int pos, int v){

     for(int i = pos; i <= k; i += lowbit(i))

         if (vis[i] == times) val[i] += v;

         else val[i] = v, vis[i] = times;

 }

 int query(int pos){

     int ans = ;

     for(int i = pos; i; i -= lowbit(i))

         if (vis[i] == times)

             ans += val[i];

     return ans;

 }

 void solve(int l,int r){

     int mid = l + r >> ;

     if (l < mid) solve(l, mid);

     sort(a + l, a + r + , cmp);

     times ++;

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

         if (a[i].id <= mid) add(a[i].z, num[a[i].id]);

         else rank[a[i].id] += query(a[i].z);

     sort(a + l, a + r + );

     if (mid +  < r) solve(mid + , r);

 }

 int main(){

     freopen("3262.in", "r", stdin);

     freopen("3262.out", "w", stdout);

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

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

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

     sort(a + , a + n + );

     for(int i = ; i <= n; i ++) b[i] = a[i];

     int cnt = ;

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

         if (b[i] != b[i - ]) a[++ cnt] = b[i], num[cnt] = ;

         else num[cnt] ++;

     for(int i = ; i <= cnt; i ++) a[i].id = i, rank[i] = num[i] - ;

 //    for(int i = 1; i <= cnt; i ++) printf("%d %d %d num = %d\n",a[i].x, a[i].y, a[i].z, num[i]);

     solve(, cnt);

 //    for(int i = 1; i <= cnt; i ++) printf("rank[%d] = %d\n",i,rank[i]);

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

         ans[rank[i]] += num[i];

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

     return ;

 }