首页 > 代码库 > 【COGS2479】 HZOI2016—偏序

【COGS2479】 HZOI2016—偏序

http://cogs.pro/cogs/problem/problem.php?pid=2479 (题目链接)

题意

  四维偏序。

Solution

  CDQ套CDQ。

细节

  第二次分治不能直接按照mid分离两类数了。

代码

// cogs2479#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483600#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=50010;int n,ans,f[maxn],c[maxn];struct data {int x,y,z,id,op;}q[maxn],nq[maxn],p[maxn],np[maxn];bool cmp(data a,data b) {return a.id<b.id;}bool CMP(data a,data b) {return a.y<b.y;}int lowbit(int x) {	return x&-x;}void modify(int x,int val) {	for (int i=x;i<=n;i+=lowbit(i)) c[i]+=val;}int query(int x) {	int res=0;	for (int i=x;i;i-=lowbit(i)) res+=c[i];	return res;}void solve2(int l,int r) {	if (l==r) return;	int mid=(l+r)>>1;	sort(p+l,p+r+1,CMP);	solve2(l,mid);solve2(mid+1,r);	for (int i=l,j=mid+1,k=l;i<=mid || j<=r;) {		if (j>r || (i<=mid && p[i].id<p[j].id)) {			if (p[i].op==0) modify(p[i].z,1);			np[k++]=p[i++];		}		else {			if (p[j].op==1) f[p[j].id]+=query(p[j].z-1);			np[k++]=p[j++];		}	}	for (int i=l;i<=mid;i++) if (p[i].op==0) modify(p[i].z,-1);	for (int i=l;i<=r;i++) p[i]=np[i];}void solve(int l,int r) {	if (l==r) {ans+=f[q[l].id];return;}	int mid=(l+r)>>1,l1=l,l2=mid+1;	for (int i=l;i<=r;i++) q[i].x<=mid ? nq[l1++]=q[i] : nq[l2++]=q[i];	for (int i=l;i<=r;i++) q[i]=nq[i];	solve(l,mid);	for (int i=l;i<=r;i++) p[i]=q[i],p[i].op=i>mid;	sort(p+l,p+r+1,cmp);	solve2(l,r);	solve(mid+1,r);}int main() {	free("partial_order");	scanf("%d",&n);	for (int i=1;i<=n;i++) scanf("%d",&q[i].x);	for (int i=1;i<=n;i++) scanf("%d",&q[i].y);	for (int i=1;i<=n;i++) scanf("%d",&q[i].z);	for (int i=1;i<=n;i++) q[i].id=i;	solve(1,n);	printf("%d",ans);	fclose(stdin);fclose(stdout);	return 0;}

 

【COGS2479】 HZOI2016—偏序