记录编号	498383	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016] 偏序	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.346 s
提交时间	2018-06-13 16:42:38	内存使用	2.77 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50005;
struct A{
	int a,b,c;
	bool t;
}a[maxn],b[maxn],t[maxn];
void CDQ1(int,int);
void CDQ2(int,int);
void add(int,int);
int query(int);
long long ans=0;
int n,c[maxn];
int main(){
	freopen("partial_order.in","r",stdin);
	freopen("partial_order.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i].a);
	for(int i=1;i<=n;i++)scanf("%d",&a[i].b);
	for(int i=1;i<=n;i++)scanf("%d",&a[i].c);
	CDQ1(1,n);
	printf("%lld",ans);
	return 0;
}
void CDQ1(int l,int r){//对位置分治
	if(l==r)return;
	int mid=(l+r)>>1;
	CDQ1(l,mid);
	CDQ1(mid+1,r);//先递归左右两边，这时左右两边已经按a排好序了
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i].a<a[j].a){
			b[k]=a[i++];
			b[k++].t=false;
		}
		else{
			b[k]=a[j++];
			b[k++].t=true;
		}
	}
	while(i<=mid){
		b[k]=a[i++];
		b[k++].t=false;
	}
	while(j<=r){
		b[k]=a[j++];
		b[k++].t=true;
	}//以上是归并排序
	for(i=l;i<=r;i++)a[i]=b[i];
	CDQ2(l,r);
}
void CDQ2(int l,int r){//对a分治
	if(l==r)return;
	int mid=(l+r)>>1;
	CDQ2(l,mid);
	CDQ2(mid+1,r);//这时左右两边已经按b排好序了
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(b[i].b<b[j].b){
			if(!b[i].t)add(b[i].c,1);
			t[k++]=b[i++];
		}
		else{
			if(b[j].t)ans+=query(b[j].c);
			t[k++]=b[j++];
		}
	}
	while(i<=mid){
		if(!b[i].t)add(b[i].c,1);
		t[k++]=b[i++];
	}
	while(j<=r){
		if(b[j].t)ans+=query(b[j].c);
		t[k++]=b[j++];
	}
	for(i=l;i<=mid;i++)if(!b[i].t)add(b[i].c,-1);
	for(i=l;i<=r;i++)b[i]=t[i];
}
void add(int x,int d){
	while(x<=n){
		c[x]+=d;
		x+=x&-x;
	}
}
int query(int x){
	int ans=0;
	while(x){
		ans+=c[x];
		x&=x-1;
	}
	return ans;
}