【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;

}