P3810 三维偏序 cdq分治

题目背景https://www.luogu.org/problemnew/show/P3810

这是一道模板题

可以使用bitset，CDQ分治，K-DTree等方式解决。

题目描述

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

说明

1≤n≤100000,1≤k≤200000 1 \leq n \leq 100000, 1 \leq k \leq 200000 1≤n≤100000,1≤k≤200000

cdq分治每次计算前一半对后一半的影响。具体地，假设三维分别是x,y,z，先按x排序。分治时每次将前半边、后半边分别按y排序。虽然现在x的顺序被打乱了，但是前半边还是都小于后半边的，所以要是只计算前半边对后半边的偏序关系，是不会受到x的影响的。维护后一半的指针i，前一半的指针j，每次将i后移一位时，若y[j]<=y[i]则不断后移j，并不断将z[j]加入树状数组。然后再查询树状数组中有多少数小于等于z[i]。最后要清空树状数组。

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e5+5;
int Tree[maxn+10];
struct node
{
    int a,b,c;
    int ans;
    int num;
};
node p[maxn];
node q[maxn];
int cnt[maxn];
bool cmpa(const node &a,const node &b)
{
    if(a.a==b.a)
    {
        if(a.b==b.b)
            return a.c<b.c;
        return a.b<b.b;
    }
    return a.a<b.a;
}
bool cmpb(const node &a,const node &b)
{
    return a.b<b.b;
}
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline int lowbit(int x)
{
    return (x&-x);
}
void add(int x,int value)
{
    for(int i=x; i<=maxn; i+=lowbit(i))
    {
        Tree[i]+=value;
    }
}
int get(int x)
{
    int sum=0;
    for(int i=x; i; i-=lowbit(i))
    {
        sum+=Tree[i];
    }
    return sum;
}
void cdq(int l,int r)
{
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    sort(q+l,q+mid+1,cmpb);
    sort(q+mid+1,q+r+1,cmpb);
    int i=l,j=mid+1;
    for(; j<=r; j++)
    {
        while(i<=mid&&q[i].b<=q[j].b)
        {
            add(q[i].c,q[i].num);
            i++;
        }
        q[j].ans+=get(q[j].c);
    }
    for(j=l; j<i;j++)
        add(q[j].c,-q[j].num);
}
int main()
{
    memset(cnt,0,sizeof(maxn));
    int n=0,n_,k;
    n_=read();
    k=read();
    for(int i=0; i<n_; i++)
    {
        p[i].a=read();
        p[i].b=read();
        p[i].c=read();
        p[i].ans=0;
    }
    sort(p,p+n_,cmpa);
    for(int i=0;i<n_;i++)
    {
        int num=0;
        if(q[n].a!=p[i].a||q[n].b!=p[i].b||q[n].c!=p[i].c)
        {
            n++;
            q[n].a=p[i].a;
            q[n].b=p[i].b;
            q[n].c=p[i].c;
            q[n].num=1;
        }
        else
            q[n].num++;
    }//得到a b c 都不同的数组  num是出现的次数
    cdq(1,n);
    for(int i=1; i<=n; i++)
    {
        cnt[q[i].ans+q[i].num-1]+=q[i].num;
    }
    for(int i=0; i<n_; i++)
    {
        printf("%d\n",cnt[i]);
    }
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+15;
struct node{
int a,b,c,w,ans;
};
map<pair<int,pair<int,int> >,int >mp;
bool cmpb(const node &a,const node &b)
{
    return a.b<b.b;
}
node p[maxn];
int tree[maxn];
int num[maxn];
inline int lowbit(int x)
{
    return (x&-x);
}
void add(int x,int value)
{
    for(int i=x;i<maxn;i+=lowbit(i))
        tree[i]+=value;
}
int get(int x)
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i))
    {
        sum+=tree[i];
    }
    return sum;
}
void cdq(int l,int r)
{
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    sort(p+l,p+mid+1,cmpb);
    sort(p+mid+1,p+r+1,cmpb);
    int i=l;
    int j=mid+1;
    for(;j<=r;j++)
    {
        while(p[i].b<=p[j].b&&i<=mid)
        {
            add(p[i].c,p[i].w);
            i++;
        }
        p[j].ans+=get(p[j].c);
    }
    i--;
    for(;i>=l;i--)
        add(p[i].c,-p[i].w);
}
int main()
{
    int n,k;
    memset(num,0,sizeof(num));
    int a,b,c;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        mp[make_pair(a,make_pair(b,c))]++;
    }
    int cnt=0;
    for(auto it=mp.begin();it!=mp.end();it++)
    {
        p[cnt].a=(it->first).first;
        p[cnt].b=(it->first).second.first;
        p[cnt].c=(it->first).second.second;
        p[cnt].w=(it->second);
        p[cnt].ans=0;
        cnt++;
    }//去重
    cdq(0,cnt-1);
    for(int i=0;i<cnt;i++)
    {
        num[p[i].ans+p[i].w-1]+=p[i].w;
    }
    for(int i=0;i<n;i++)
    {
        printf("%d\n",num[i]);
    }
    return 0;
}