记录编号	322486	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016] 偏序	最终得分	100
用户昵称	喵喵喵	是否通过	通过
代码语言	C++	运行时间	1.853 s
提交时间	2016-10-15 09:52:59	内存使用	4.29 MiB

#include<cstdio>
#define maxn 50010 
#define lb(x) (x&(-x))
struct node{
	int x,y,z,op;
}q[maxn],q1[maxn],q2[maxn];
struct dfs{
	int l,r;
}sx[maxn<<2];
int n,ans,now,c[maxn];
void add(int i,int x){
	while(i<=n){
		c[i]+=x;
		i+=lb(i);
	}
}
int ask(int i){
	int res=0;
	while(i>0){
		res+=c[i];
		i-=lb(i);
	}
	return res;
}
void dfs_(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	dfs_(l,mid),dfs_(mid+1,r);
	sx[++now]=(dfs){l,r};
	return;
}
void cdq(int l,int r){
	if(l>=r) return;
	int mid=(l+r)>>1,i,j,k;
	cdq(l,mid),cdq(mid+1,r);
	for(i=l,j=mid+1,k=l;i<=mid&&j<=r;){
		if(q1[i].y<q1[j].y){
			if(!q1[i].op) add(q1[i].x,1);
			q2[k++]=q1[i++];
		}
		else{
			if(q1[j].op) ans+=ask(q1[j].x-1);
			q2[k++]=q1[j++];
		} 			    
	}
	while(j<=r){
		if(q1[j].op) ans+=ask(q1[j].x-1);
		q2[k++]=q1[j++];
	}
	while(i<=mid) q2[k++]=q1[i++];
	for(i=l,j=mid+1;i<=mid&&j<=r;){
		if(q1[i].y<q1[j].y){
			if(!q1[i].op) add(q1[i].x,-1);
			i++;
		}
		else j++;
	}
	for(i=l;i<=r;i++) q1[i]=q2[i];
	return;
} 
void in(int &x){
	static int ch;
	while((ch=getchar())<48);x=ch-'0';
	while((ch=getchar())>47) x=x*10+ch-'0';
}
int main(){
	freopen("partial_order.in","r",stdin);
	freopen("partial_order.out","w",stdout);
	in(n);
	for(int i=1;i<=n;i++) in(q[i].x);
	for(int i=1;i<=n;i++) in(q[i].y);
	for(int i=1;i<=n;i++) in(q[i].z);
	dfs_(1,n);
	for(int l,r,mid,cnt,i,j,k,tt=1;tt<=now;tt++){
		l=sx[tt].l,r=sx[tt].r,mid=(l+r)>>1,cnt=0;
		for(i=l,j=mid+1;i<=mid&&j<=r;){
			if(q[i].z<q[j].z) q[i].op=0,q1[++cnt]=q[i++];
			else 			  q[j].op=1,q1[++cnt]=q[j++];
		}
		while(j<=r) q[j].op=1,q1[++cnt]=q[j++];
		cdq(1,cnt);
		for(i=l,j=mid+1,k=l;i<=mid&&j<=r;){
			if(q[i].z<q[j].z) q1[k++]=q[i++];
			else 			  q1[k++]=q[j++];
		}
		while(i<=mid) q1[k++]=q[i++];
		while(j<=r)   q1[k++]=q[j++];
		for(i=l;i<=r;i++) q[i]=q1[i];
	}
	printf("%d\n",ans);
	return 0;
}