记录编号	359194	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016] 偏序	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	12.035 s
提交时间	2016-12-21 11:16:31	内存使用	6.78 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,split,root,data[N][3];
struct point{
	int a[3];//point 
	int l[3],r[3];//range 
	int lc,rc,split;//left child, right child and split
	int sum,k;//range data
}p[N];
bool cmp(const point &x,const point &y){
	return x.a[split]<y.a[split];
}
int build(int L,int R,int h){
	if (L>R) return 0;
	int mid=(L+R)>>1;
	split=h%3;
	sort(p+L,p+R+1,cmp);
	p[mid].split=split;
	for (int i=0;i<3;i++)
		p[mid].l[i]=p[mid].r[i]=p[mid].a[i];
	int lc=p[mid].lc=build(L,mid-1,h+1);
	/*for (int i=0;i<h;i++) putchar(' ');
	for (int i=0;i<3;i++) printf("%d ",p[mid].a[i]);
	puts("");*/
	int rc=p[mid].rc=build(mid+1,R,h+1);
	if (lc){
		for (int i=0;i<3;i++)
			p[mid].l[i]=min(p[mid].l[i],p[lc].l[i]),
			p[mid].r[i]=max(p[mid].r[i],p[lc].r[i]);
	}
	if (rc){
		for (int i=0;i<3;i++)
			p[mid].l[i]=min(p[mid].l[i],p[rc].l[i]),
			p[mid].r[i]=max(p[mid].r[i],p[rc].r[i]);
	}
	return mid;
}
bool check(int x[],int a[]){//x<a返回1 
	for (int i=0;i<3;i++)
	if (x[i]>=a[i]) return 0;
	return 1;
}
int sum(int x,int a[]){
	if (check(p[x].r,a)) return p[x].sum;
	int ans=0,lc=p[x].lc,rc=p[x].rc;
	if (check(p[x].a,a)) ans+=p[x].k;
	if (lc&&check(p[lc].l,a)) ans+=sum(lc,a);
	if (rc&&check(p[rc].l,a)) ans+=sum(rc,a);
	return ans;
}
void add(int x,int a[]){
	p[x].sum++;
	int X=p[x].a[p[x].split],Y=a[p[x].split];
	if (Y==X) p[x].k++;
	if (Y>X) add(p[x].rc,a);
	if (Y<X) add(p[x].lc,a);
}
int main()
{
	freopen("partial_order.in","r",stdin);
	freopen("partial_order.out","w",stdout);
	scanf("%d",&n);
	for (int j=0;j<3;j++)
	for (int i=1;i<=n;i++){
		scanf("%d",&data[i][j]);
		p[i].a[j]=data[i][j];
	}
	root=build(1,n,0);
	long long ans=0;
	for (int i=1;i<=n;i++){
		ans+=sum(root,data[i]);
		add(root,data[i]);
	}
	printf("%lld\n",ans);
	return 0;
}