Jam's problem again

原题：Jam’s problem again

原题大意

给出n个坐标(x,y,z)，如果有两个点(xi,yi,zi) 和 (xj,yj,zj)满足 xi≥xj，yi≥yj，zi≥zj，那么i这个点的等级就加一,最后输出每个点的等级。

算法分析

三维偏序，模板题，CDQ分治加树状数组，最后注意处理两个点完全相同的情况。

程序代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = 100000+100;
const int N = 100010;
struct po{
    int x, y, z, id;

}a[maxn],b[maxn];
int ans[maxn];
int C[maxn*2];
int T, n;
bool cmp1(po a, po b){
    if(a.x != b.x) return a.x < b.x;
    if(a.y != b.y) return a.y < b.y;
    return a.z < b.z;
}
bool cmp2(po a, po b){
    if(a.y!=b.y) return a.y < b.y;
    return a.z < b.z;
}


int lowbit(int x){
    return x&(-x);
}
void update(int x){
    while(x <=N){
        C[x]++;
        x+=lowbit(x);
    }
}

int query(int x){
    int sum = 0;
    while(x){
        sum+=C[x];
        x-=lowbit(x);
    }
    return sum;
}
void reset(int x){
   while(x<=N){
       C[x]=0;
       x+=lowbit(x);
   }
}
void cdq(int l, int r){
    if(l == r) return;
    int mid = (l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    for(int i =l; i <= r; i++) b[i] = a[i];
    sort(b+l,b+mid+1,cmp2);
    sort(b+mid+1,b+r+1,cmp2);
    int j = l;
    for(int i = mid+1; i <= r; i++){
        while(j<=mid && b[j].y <= b[i].y ){
            update(b[j].z);
            j++;
        }
        ans[b[i].id] +=query(b[i].z);
    }
   for(int i = l; i <= mid; i++)
       reset(b[i].z);
    return ;
}

int main(){
//freopen("input.txt", "r", stdin);
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        mem(ans,0);
        mem(C,0);
        for(int i = 1; i <= n; i++){
            int x, y, z;
            scanf("%d%d%d",&x, &y, &z);
            a[i] = (po){x,y,z,i};
        }
        sort(a+1,a+n+1,cmp1);
        cdq(1,n);
        for(int i = n-1; i >= 1; i--)
            if((a[i].x == a[i+1].x) && (a[i].y == a[i+1].y)&&(a[i].z==a[i+1].z))
                ans[a[i].id] = ans[a[i+1].id];
        for(int i = 1; i <= n; i++)
            printf("%d\n", ans[i]);
    }
    return 0;
}