经典问题：三维偏序

题：https://www.luogu.org/problem/P3810

一般处理：先按照自己定义的第一维排好序，那么在接下来的俩维判断中，我们就可以消除第一维造成的影响，接着用以前学过的分治排序法来处理第二维，以第二维作为排序对象，对于分治的[l,midd]和[midd+1,r]这俩个区间

对于区间 [m+1, r]中的某个元素x，将区间 [l, m] 的第二维小于x的元素的按第三维的权值加入树状数组，

最后区间 [l, m] 对区间 x 的贡献就是查询树状数组中小于x第三维的个数

可以边进行分治边进行归并排序，树状数组要及时清空

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
    int sum=0,x=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            x=0;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();
    return x?sum:-sum;
}
inline void write(ll x){
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
#define pb push_back
#define lowbit(x) (x&(-x))
const int M=2e5+5;
struct node{
    int x,y,z,cnt,ans;
    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>>1],temp[M>>1];
int tree[M];
int n,k;
int ANS[M];
void add(int i,int x){
    while(i<=k){
        tree[i]+=x;
        i+=lowbit(i);
    }
}
int query(int i){
    int res=0;
    while(i){
        res+=tree[i];
        i-=lowbit(i);
    }
    return res;
}
void cdq(int l,int r){
    if(l==r){
        a[l].ans+=a[l].cnt-1;
        return ;
    }
    int midd=(l+r)>>1;
    cdq(l,midd);
    cdq(midd+1,r);
    int i=l,j=midd+1,op=l;
    while(j<=r){
        while(i<=midd&&a[i].y<=a[j].y){
            add(a[i].z,a[i].cnt);
            temp[op++]=a[i];
            i++;
        }
        a[j].ans+=query(a[j].z);
        temp[op++]=a[j];
        j++;
    }
    for(j=l;j<i;j++)
        add(a[j].z,-a[j].cnt);
    while(i<=midd)
        temp[op++]=a[i],i++;
    
    for(i=l;i<=r;i++)
        a[i]=temp[i];
}
int main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++)
        a[i].x=read(),a[i].y=read(),a[i].z=read();
    sort(a+1,a+1+n);
    int now=1,cnt=0;
    for(int i=2;i<=n;i++){
        if(a[i-1].x==a[i].x&&a[i-1].y==a[i].y&&a[i-1].z==a[i].z)
            now++;
        else{
            a[++cnt]=a[i-1];
            a[cnt].cnt=now;
            a[cnt].ans=0;
            now=1;
        }
        
    }
    a[++cnt]=a[n];
    a[cnt].cnt=now;
    a[cnt].ans=0;
    cdq(1,cnt);
    for(int i=1;i<=cnt;i++)
        ANS[a[i].ans]+=a[i].cnt;
    for(int i=0;i<n;i++)
        printf("%d\n",ANS[i]);
    return 0;    
}

View Code