偏序关系CDQ BZOJ 3262 陌上花开

向右看齐 2022-05-15 01:11 155阅读 0赞

[陌上花开，可缓缓归矣][Link 1]

偏序关系就是按照某个条件的排序关系，这个题是三维偏序关系，然后给这些花划分等级，也就是说,A(x, y, z) 比A'(x',y',z')等级高的话 那么就满足x>=x', y>=y', z>=z'。我们只要统计一下比自己等级低的有几个，按照这个数量做一个等级归纳排序，输出每个等级的个数就解决了。

解决这类问题可以用cdq+树状数组，首先我们对x排序，然后在x序上进行归并，将y排序，用树状数组统计z，意思就是，归并时，我们只需要统计出对于右边的块中的y，z，左边块有多少花小于他。因为将y排好序了，所以只需要从左到右用树状数组维护左边块中z的值就好了，遇到右边块的元素就询问有多少小于他的。还要注意的就是三个值相同的花可以互相提升等级，这样我们需要事先从大到小处理一下。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e5+10;
    int n, k, rk[N], s[N<<1];
    struct flower{
        int s, c, m;
        int id, rk;
    }f[N], a[N];
    bool cmp(flower a, flower b){
        return (a.s<b.s) || (a.s==b.s && a.c<b.c) || (a.s==b.s && a.c==b.c && a.m<b.m);
    }
    bool operator == (flower a, flower b){
        return a.s==b.s&&a.c==b.c&&a.m==b.m;
    }
    
    int sum(int x){
        int ret=0;
        for(; x>0; x-=x&-x)
            ret+=s[x];
        return ret;
    }
    void upd(int x, int v){
        for(; x<2*N; x+=x&-x)
            s[x]+=v;
    }
    
    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, L=l, R=mid+1; i<=r; i++){
            if(L<=mid && (R>r || f[L].c<=f[R].c))
                a[i]=f[L++];
            else
                a[i]=f[R++];
        }
    
        for(int i=l; i<=r; i++){
            f[i]=a[i];
            if(a[i].id<=mid)
                upd(a[i].m, 1);
            else{
                f[i].rk+=sum(a[i].m);
            }
        }
    
        for(int i=l; i<=r; i++)
            if(a[i].id<=mid) upd(a[i].m, -1);
    }
    
    int main(){
        scanf("%d%d", &n, &k);
        for(int i=1; i<=n; i++){
            scanf("%d%d%d", &f[i].s, &f[i].c, &f[i].m);
        }
        sort(f+1, f+1+n, cmp);
        flower t=(flower){-1,-1,-1,-1,-1};
        int cnt=0;
        for(int i=n; i>=1; i--){
            f[i].id=i;
            if(f[i]==t){
                f[i].rk=++cnt;
            }
            else{
                cnt=0;
                f[i].rk=0;
            }
            t=f[i];
        }
    
        cdq(1, n);
        for(int i=1; i<=n; i++)
            rk[f[i].rk]++;
        for(int i=0; i<n; i++)
            printf("%d\n", rk[i]);
        return 0;
    }
    /*
    4 3
    1 2 3
    2 2 2
    1 2 3
    1 2 3
    */

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=3262