102606C. Coronavirus Battle time limit per test4 seconds（三维拓扑序）

题：https://codeforces.com/gym/102606/problem/C

题意：给出n，k1，k2，然后题目给出n个点的转化，给出定义:在三维空间内，i 能保护 j 当且仅当 xi<=xj&&yi<=yj&&zi<=zj(且题目保证没有共点)，每一轮没被保护的点都会消失，问每个点什么时候消失；

分析：采用cdq分治，求拓扑序

例如 第3个样例离散化后：

3 5 4
1 4 2
5 1 1
2 2 3
4 3 5

这5个点的拓扑序为1 0 0 0 1，虽说第4个和第2个都比第1个数小，但第4个和第2个数的拓扑序为0，（要区分以前写的cdq分治）

#include<bits/stdc++.h>
#define lowbit(i) i&(-i)
using  namespace std;
typedef unsigned long long ll;
const int M=2e5+5;
ll x[M],y[M],z[M];
int tree[M<<1],ans[M];
int n;
struct node{
    ll x,y,z;
    int id,ans,cnt;
    bool operator < (const node &b)const{
        if(x!=b.x)
            return x<b.x;
        else if(y!=b.y)
            return y<b.y;
        else
            return z<b.z;
    }
}a[M],temp[M];
void add(int pos,int val){
    while(pos<M)
        tree[pos]=max(tree[pos],val),pos+=lowbit(pos);
}
void del(int x){
    for(int i=x;i<M;i+=lowbit(i))
        tree[i]=0;
}
int query(int pos){
    int res=0;
    while(pos)
        res=max(res,tree[pos]),pos-=lowbit(pos);
    return res;
}
bool cmp1(node p,node q){
    return p.x<q.x;
}
bool cmp2(node p,node q){
    return p.id<q.id;
}
void cdq(int l,int r){
    int midd=(l+r)>>1;
    if(l==r)
        return;
    cdq(l,midd);
    sort(a+l,a+midd+1,[&](node A,node B){
         return A.y<B.y;
    });
    sort(a+midd+1,a+r+1,[&](node A,node B){
         return A.y<B.y;
    });
    int t1=l,t2=midd+1;
    for(int i=l;i<=r;i++){
        if((t1<=midd&a[t1].y<=a[t2].y)||t2>r){
            add(a[t1].z,ans[a[t1].id]);
            t1++;
        }
        else{
            ans[a[t2].id]=max(ans[a[t2].id],query(a[t2].z)+1);
            t2++;
        }
    }
    for(int i=l;i<=midd;i++)
        del(a[i].z);
    sort(a+midd+1,a+r+1,[&](node A,node B){
         return A.x<B.x;
    });
    cdq(midd+1,r);
}
void init(){
    sort(x+1,x+1+n);
    int m=unique(x+1,x+1+n)-x-1;
    for(int i=1;i<=n;i++)
        a[i].x=lower_bound(x+1,x+1+m,a[i].x)-x;
    sort(y+1,y+1+n);
    m=unique(y+1,y+1+n)-y-1;
    for(int i=1;i<=n;i++)
        a[i].y=lower_bound(y+1,y+1+m,a[i].y)-y;
    sort(z+1,z+1+n);
    m=unique(z+1,z+1+n)-z-1;
    for(int i=1;i<=n;i++)
        a[i].z=lower_bound(z+1,z+1+m,a[i].z)-z;
}
unsigned long long k1, k2;
unsigned long long CoronavirusBeats() {
    unsigned long long k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}
int main(){
    scanf("%d%llu%llu",&n,&k1,&k2);
    for(int i=1;i<=n;i++)
        ans[i]=1;
    for(int i=1;i<=n;i++){
        x[i] = CoronavirusBeats();
        y[i] = CoronavirusBeats();
        z[i] = CoronavirusBeats();
        a[i].x=x[i],a[i].y=y[i],a[i].z=z[i],a[i].cnt=1,a[i].id=i;
    }
    init();
    
    sort(a+1,a+1+n,[&](node A,node B){
         return A.x<B.x;
    });
    /*int now=0;
    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)
            now++;
        else
            now=0;
        ans[a[i].id]+=now;
    }*/
    cdq(1,n);
    int maxx=0;
    for(int i=1;i<=n;i++){
        maxx=max(maxx,ans[i]);
        ans[i]--;
    }
    printf("%d
",maxx);
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}