本文主要是介绍P3810 三维偏序 cdq分治，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目背景https://www.luogu.org/problemnew/show/P3810
这是一道模板题
可以使用bitset，CDQ分治，K-DTree等方式解决。
题目描述
输入输出样例
输入样例#1： 复制
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1输出样例#1： 复制
3
1
3
0
1
0
1
0
0
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;}elseq[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;
}
这篇关于P3810 三维偏序 cdq分治的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
