三维偏序·CDQ分治+树状数组

题目传送门

更好的阅读体验

题目大意

• 给定个点，求对于每个点,有多少个点满足

题解

• 由于点能够重复，得先去重，记录一下每个点的个数
• 先按照排序
• 然后分治处理
• 对于一段区间，将它从中点处分开，考虑对于左半区间的点答案都已经维护好，但是右半区间可能会产生跨中点的答案，需要我们在合并的时候加上。
• 我们可以对两个区间按排序，维护两个指针分别指向两段区间的头 如果 ,那么将 添加到树状数组中,一直做下去直到，然后在树状数组中查询比小的点有多少个加到的答案中去。
• 值得注意的一点是每算完一个的答案，都要将树状数组恢复原样，我们只需在改动的位置上加上负的改变量即可。

复杂度

• 一个分治里用树状数组 大概是的样子 QAQ

代码实现

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,nn,k,f[200005];
struct node{
    int x,y,z,ans,w;
}a[100005],b[100005];
struct TREE{
    int tre[200005],kk;
    int lowbit(int x){
        return x&(-x);
    }
    int ask(int i){
        int ans=0;
        for(;i;i-=lowbit(i)) ans+=tre[i];
        return ans;
    }
    void add(int i,int k){
        for(;i<=kk;i+=lowbit(i)) tre[i]+=k;
    }
}t;
bool cmp1(node a,node b){
    if(a.x==b.x){
        if(a.y==b.y) return a.z<b.z;
        return a.y<b.y;
    }
    return a.x<b.x;
}
bool cmp2(node a,node b){
    if(a.y==b.y) return a.z<b.z;
    return a.y<b.y;
}
void cdq(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    sort(a+l,a+mid+1,cmp2);
    sort(a+mid+1,a+r+1,cmp2);
    int i=mid+1,j=l;
    while(i<=r){
        while(a[j].y<=a[i].y&&j<=mid){
            t.add(a[j].z,a[j].w);
            j++;
        }
        a[i].ans+=t.ask(a[i].z);
        i++;
    }
    for(i=l;i<j;i++)t.add(a[i].z,-a[i].w);
}
int main(){
    scanf("%d%d",&nn,&k);
    t.kk=k;
    for(int i=1;i<=nn;i++)
        scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z);
    sort(b+1,b+nn+1,cmp1);
    int res=0;
    for(int i=1;i<=nn;i++){
        res++;
        if(b[i].x!=b[i+1].x||b[i].y!=b[i+1].y||b[i].z!=b[i+1].z) a[++n]=b[i],a[n].w=res,res=0;
    }
    cdq(1,n);
    for(int i=1;i<=n;i++)
        f[a[i].ans+a[i].w-1]+=a[i].w;
    for(int i=0;i<nn;i++) printf("%d\n",f[i]);
    return 0;
}