记录编号	586600	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016] 偏序	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	2.941 s
提交时间	2024-02-16 23:43:42	内存使用	12.30 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e4+10;
int n,m;
struct made{
	int a,b,c;
	bool f;//1l  0r 
}a[N],c[N];
bool cmp1(made x,made y){
	return x.a < y.a;
}
bool cmp2(made x,made y){
	return x.b < y.b;
}
struct BIT{
	int c[N];
	int lowbit(int x){return (x & (-x));}
	void add(int x,int val){
		for(;x <= n;x += lowbit(x))c[x] += val;
	}
	ll ask(int x){
		ll ans = 0;
		for(;x > 0;x -= lowbit(x))ans += c[x];
		return ans;
	} 
}t;
ll ans;
void CDQ3d(int l,int r){
	if(l == r)return;
	int mid = l + r >> 1;
	CDQ3d(l,mid),CDQ3d(mid+1,r);
	sort(c+l,c+mid+1,cmp2),sort(c+mid+1,c+r+1,cmp2);
	int i = l,j = mid+1;
	while(j <= r){
		while(i <= mid && c[i].b < c[j].b){
			if(c[i].f)t.add(c[i].c,1); 
			i++;
		}
		if(!c[j].f)ans += t.ask(c[j].c-1);
		j++;
	} 
	for(int u = l;u < i;u++)
		if(c[u].f)t.add(c[u].c,-1);
}//二维CDQ 
void CDQ2d(int l,int r){//
	if(l == r)return;
	int mid = l + r >> 1;
	CDQ2d(l,mid),CDQ2d(mid+1,r);
	sort(a+l,a+mid+1,cmp1),sort(a+mid+1,a+r+1,cmp1);
	int i = l,j = mid+1,k = l;
	while(j <= r){
		while(i <= mid && a[i].a < a[j].a)a[i].f = 1,c[k++] = a[i++];
		a[j].f = 0,c[k++] = a[j++];
	}
	while(i <= mid)a[i].f = 1,c[k++] = a[i++];
	CDQ3d(l,r);
}
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);
	CDQ2d(1,n);
	printf("%lld\n",ans);

	return 0;
	
}