P3810 【模板】三维偏序（陌上花开）

P3810 【模板】三维偏序（陌上花开）

cdq分治+树状数组

三维偏序模板题

前两维用cdq分治，第三维用树状数组进行维护

就像用树状数组搞逆序对那样做--->存权值的出现次数

attention：当两个元素完全相同时要重复计算

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
template <typename T> inline void read(T &x){
    char c=getchar(); x=0; bool f=1;
    while(!isdigit(c)) f= !f||c=='-' ? 0:1,c=getchar();
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x= f? x:-x;
}int wt[50];
template <typename T> inline void output(T x){
    if(!x) {putchar(48); return ;}
    if(x<0) putchar('-'),x=-x; int l=0;
    while(x) wt[++l]=x%10,x/=10;
    while(l) putchar(wt[l--]+48);
}
struct data{
    int x,y,z,ans,w;
    bool operator < (const data &tmp) const{
        return (x<tmp.x||(x==tmp.x&&y<tmp.y)||(x==tmp.x&&y==tmp.y&&z<tmp.z));
    }
}a[100002],b[100002];
int n,k,cnt,lev[100002];
struct tree_array{ //树状数组
    int t[200002];
    inline void add(int x,int p) {for(;x<=k;x+=x&-x)t[x]+=p;}
    inline int sum(int x) {int res=0; for(;x;x-=x&-x)res+=t[x]; return res;}
}mo1;
inline void cdq(int l,int r){ //cdq分治
    int mid=l+((r-l)>>1);
    if(l==r) return ;
    cdq(l,mid); cdq(mid+1,r);
    int t1=l,t2=mid+1;
    for(int i=l;i<=r;++i){
        if((t1<=mid&&a[t1].y<=a[t2].y)||t2>r) mo1.add(a[t1].z,a[t1].w),b[i]=a[t1++]; //注意可以取到等号
        else a[t2].ans+=mo1.sum(a[t2].z),b[i]=a[t2++];
    }
    for(int i=l;i<=mid;++i) mo1.add(a[i].z,-a[i].w); //记得清空树状数组
    for(int i=l;i<=r;++i) a[i]=b[i];
}
int main(){
    read(n); read(k);
    for(int i=1;i<=n;++i) read(a[i].x),read(a[i].y),read(a[i].z),a[i].w=1;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i){
        if(i==1||a[i-1]<a[i]) a[++cnt]=a[i];
        else ++a[cnt].w; //去重（当然后面要加回来）
    }cdq(1,cnt);
    for(int i=1;i<=cnt;++i) lev[a[i].ans+a[i].w]+=a[i].w; //把重复的加回来 
    for(int i=1;i<=n;++i) output(lev[i]),putchar('
');
    return 0;
}