首页 > 代码库 > COGS 2479. [HZOI 2016]偏序 [CDQ分治套CDQ分治 四维偏序]
COGS 2479. [HZOI 2016]偏序 [CDQ分治套CDQ分治 四维偏序]
传送门
给定一个有n个元素的序列，元素编号为1~n，每个元素有三个属性a,b,c，求序列中满足i<j且ai<aj且bi<bj且ci<cj的数对(i,j)的个数。
对于100%的数据，1<=n<=50000，保证所有的ai、bi、ci分别组成三个1~n的排列。
$CDQ$分治套$CDQ$分治也不是很难嘛
对于本题，设四维$a,b,c,d$
$Sort\ at\ a$
$CDQ(l,r)$
$\quad CDQ(l,mid)$
$\quad CDQ(mid+1,r)$
$\quad Merge_Sort\ at\ b$ 每个元素标记属于$[l,mid]\or\ [mid+1,r]$
$\quad CDQ2(l,r)$
$CDQ2(l,r)$要做的就是按时间序维护一个二维点集$(c,d)$ 加点与询问一个范围内点的个数
和普通的三维偏序一样，就是多了一个标记的限制(来自$CDQ$中$a$的限制，必须用标记不能判断$a \le mid$，因为$CDQ2$是要递归下去的，$mid$就变了)
有一个时间序$b$和限制$a$，然后$c$归并排序，$d$树状数组维护
完成啦！
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long ll;const int N=5e4+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n;struct Operation{ int a,b,c,d; bool flag;}a[N],t1[N],t2[N];int c[N];inline int lowbit(int x){return x&-x;}inline void add(int p,int v){for(;p<=n;p+=lowbit(p)) c[p]+=v;}inline int sum(int p){ int re=0; for(;p;p-=lowbit(p)) re+=c[p]; return re;}int ans;void CDQ2(int l,int r){ if(l==r) return; int mid=(l+r)>>1; CDQ2(l,mid);CDQ2(mid+1,r); int i=l,j=mid+1,p=l; Operation *a=t1,*t=t2; while(i<=mid||j<=r){ if(j>r||(i<=mid&&a[i].c<a[j].c)){ if(a[i].flag) add(a[i].d,1); t[p++]=a[i++]; }else{ if(!a[j].flag) ans+=sum(a[j].d); t[p++]=a[j++]; } } for(int i=l;i<=mid;i++) if(a[i].flag) add(a[i].d,-1); for(int i=l;i<=r;i++) a[i]=t[i];}void CDQ(int l,int r){ if(l==r) return; int mid=(l+r)>>1; CDQ(l,mid);CDQ(mid+1,r); int i=l,j=mid+1,p=l; Operation *t=t1; while(i<=mid||j<=r){ if(j>r||(i<=mid&&a[i].b<a[j].b)) (t[p++]=a[i++]).flag=1; else (t[p++]=a[j++]).flag=0; } for(int i=l;i<=r;i++) a[i]=t[i]; CDQ2(l,r);}int main(){ freopen("partial_order.in","r",stdin); freopen("partial_order.out","w",stdout); n=read(); for(int i=1;i<=n;i++) a[i].b=read(); for(int i=1;i<=n;i++) a[i].c=read(); for(int i=1;i<=n;i++) a[i].d=read(),a[i].a=i; CDQ(1,n); printf("%d",ans);}
COGS 2479. [HZOI 2016]偏序 [CDQ分治套CDQ分治 四维偏序]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。