洛谷P3810(陌上花开)(三维偏序,cdq分治)
程序员文章站
2022-05-14 18:41:51
...
洛谷P3810(陌上花开)(三维偏序,cdq分治)
题目链接:传送门
思路:
PS:cdq是一种思路,因为最早是被陈丹琦引入国内的,所以就叫 cdq 分治了。
本题中的三维偏序可以取等号,所以需要注意(a,b,c)相等的情况。这时不能定义顺序,所以我们记录该元组的数量即可。
对于每个元组,我们先记录严格小于(a,b,c)元组的数量,再加上与之相等元组的数量就是这个小于等于指这个元组答案。
所以我们先将所有元组按a,b,c分别为第一,第二,第三关键字进行从小到大排序。那么对于第i个元组,严格小于这个元素的元组只会在 左边。然后进行cdq分治。
对于区间 的计算,假设区间中点为m,对于每个偏序对i,j分为三种情况。
- $ m+1\le i,j\le r$
那么第一种情况的偏序对,我们用来计算,第三种情况的偏序对我们用来计算。
对于第二种情况的偏序对,我们可以让左区间按从小到大排序,右区间从小到大排序。遍历右区间的所有元素,假设为第个元素,那么找到左区间满足小于等于 的,统计其小等于的数量。但是右区间我们对b进行了排序操作,所以其是非递减的,所以我们可以使用双指针来统计, 树状数组来维护。
注意:因为树状数组是重复使用的,所以每次我们要执行之前添加的逆过程来清空树状数组。
代码:
#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=1e5+20;
int MXN;
int bt[200005],f[N];
int lowbit(int k)
{
return k&-k;
}
void modify(int k,int cnt)
{
while(k<=MXN)
{
bt[k]+=cnt;
k+=lowbit(k);
}
}
int getpre(int k)
{
int sum=0;
while(k)
{
sum+=bt[k];
k-=lowbit(k);
}
return sum;
}
struct node{
int a,b,c,cnt,sum;
}t[N];//用来保证 a不同
bool cmp(const node &a,const node &b)
{
if(a.a!=b.a) return a.a<b.a;
if(a.b!=b.b) return a.b<b.b;
return a.c<b.c;
}
bool cmpb(const node &a,const node &b)
{
return a.b<b.b;
}
void cdq(int l,int r)
{
if(l==r) return ;
int m=(l+r)>>1;
cdq(l,m);
cdq(m+1,r);
sort(t+l,t+m+1,cmpb);
sort(t+m+1,t+r+1,cmpb);
int p=l-1;
for(int i=m+1;i<=r;++i){
//把所有<=t[i].b的元素全加
while(p+1<=m&&t[p+1].b<=t[i].b){
++p;
modify(t[p].c,t[p].cnt);
}
t[i].sum+=getpre(t[i].c);
}
for(int i=l;i<=p;++i) modify(t[i].c,-t[i].cnt);
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
int n;
cin>>n>>MXN;
for(int i=1;i<=n;++i)
{
int a,b,c;
cin>>t[i].a>>t[i].b>>t[i].c;
t[i].cnt=1;
t[i].sum=0;
}
int last=0;
sort(t+1,t+n+1,cmp);
for(int i=1;i<=n;++i)
{
if(!last) {
t[++last]=t[i];
}
else if( t[last].a==t[i].a && t[last].b==t[i].b &&t[last].c==t[i].c )
t[last].cnt++;
else
t[++last]=t[i];
}
cdq(1,last);
for(int i=1;i<=last;++i) t[i].sum+=t[i].cnt;
for(int i=1;i<=last;++i) f[t[i].sum]+=t[i].cnt;
for(int i=1;i<=n;++i) cout<<f[i]<<endl;
return 0;
}
推荐阅读
-
陌上花开 HYSBZ - 3262 三维偏序问题 CDQ分治+树状数组
-
BZOJ 3262: 陌上花开 (cdq分治,三维偏序)
-
bzoj 3262 :陌上花开 (cdq分治 三维偏序)
-
【bzoj3262】陌上花开(cdq分治解决三维偏序问题)一些总结
-
BZOJ - 3262 陌上花开 CDQ分治 三维偏序
-
BZOJ 3262 陌上花开 三维偏序,CDQ分治
-
三维偏序(陌上花开)---洛谷P3810&&BZOJ3262(cdq分治--归并排序+树状数组)
-
P3810 -三维偏序(陌上花开)cdq-分治
-
Luogu P3810 【模板】三维偏序(陌上花开) CDQ分治 树状数组
-
CDQ分治--模板 BZOJ 3262--陌上花开【三维偏序】