记录编号	365066	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]偏序 II	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	9.875 s
提交时间	2017-01-19 13:58:17	内存使用	7.16 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct cdq1{int a,b,c,d,tp;}Q[N],Q1[N];
bool cmp1(const cdq1 &x,const cdq1 &y){return x.a<y.a;}
struct cdq2{int b,c,d,tp;}Q2[N];
bool cmp2(const cdq2 &x,const cdq2 &y){return x.b<y.b;}
struct cdq3{int c,d,tp;}Q3[N];
bool cmp3(const cdq3 &x,const cdq3 &y){return x.c<y.c;}
int n,a[N];ll ans;
//tp=-1表示只计算贡献,tp=1表示只计算答案,tp=0表示无效 
void add(int p,int d){
	for (;p<=n;p+=p&-p) a[p]+=d;
}
int sum(int r){
	int ans=0;
	for (;r;r-=r&-r) ans+=a[r];
	return ans;
}
void CDQ3(int l,int r){
	if (l==r) return;
	int mid=(l+r)>>1,cnt=0;
	for (int i=l;i<=mid;i++)
		if (Q2[i].tp==-1) Q3[++cnt]=(cdq3){Q2[i].c,Q2[i].d,-1};
	for (int i=mid+1;i<=r;i++)
		if (Q2[i].tp==1) Q3[++cnt]=(cdq3){Q2[i].c,Q2[i].d,1};
	sort(Q3+1,Q3+cnt+1,cmp3);
	for (int i=1;i<=cnt;i++)
		if (Q3[i].tp==-1) add(Q3[i].d,1);
			else ans+=sum(Q3[i].d);
	for (int i=1;i<=cnt;i++)
		if (Q3[i].tp==-1) add(Q3[i].d,-1);
	CDQ3(l,mid);CDQ3(mid+1,r);
}
void CDQ2(int l,int r){
	if (l==r) return;
	int mid=(l+r)>>1;
	for (int i=l;i<=mid;i++)
		Q2[i]=(cdq2){Q1[i].b,Q1[i].c,Q1[i].d,Q1[i].tp==-1?-1:0};
	for (int i=mid+1;i<=r;i++)
		Q2[i]=(cdq2){Q1[i].b,Q1[i].c,Q1[i].d,Q1[i].tp==1?1:0};
	sort(Q2+l,Q2+r+1,cmp2);
	CDQ3(l,r);
	CDQ2(l,mid);CDQ2(mid+1,r);
}
void CDQ1(int l,int r){
	if (l==r) return;
	int mid=(l+r)>>1;
	for (int i=l;i<=mid;i++) Q1[i]=Q[i],Q1[i].tp=-1;
	for (int i=mid+1;i<=r;i++) Q1[i]=Q[i],Q1[i].tp=1;
	sort(Q1+l,Q1+r+1,cmp1);
	CDQ2(l,r);
	CDQ1(l,mid);CDQ1(mid+1,r);
}
int main()
{
	freopen("partial_order_two.in","r",stdin);
	freopen("partial_order_two.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&Q[i].a);
	for (int i=1;i<=n;i++) scanf("%d",&Q[i].b);
	for (int i=1;i<=n;i++) scanf("%d",&Q[i].c);
	for (int i=1;i<=n;i++) scanf("%d",&Q[i].d);
	CDQ1(1,n);
	printf("%lld\n",ans);
	return 0;
}