BZOJ 4430 [Nwerc2015]Guessing Camels赌骆驼

题目大意

给你三个长度为$N$的序列$A,B,C$，求有多少数对$<i,j>$满足$A_i<A_j,B_i<B_j,C_i<C_j$.

有点神的题……

两个数在不满足性质的情况会发生什么？如果两两数组比较是否两个数出现次序一样就会发现有两次Query的结果是False,一次查询的结果是True.

之后就很简单了。对三个数组两两求次序不一样的数对个数，之后/2就得到了所有数对次序不同的个数。 用数对总数减一下就好了。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
inline char nc()
{
	static char buf[100000],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int RI()
{
	int ret=0;char tmp=nc();
	while(!isdigit(tmp)) tmp=nc();
	while(isdigit(tmp)) ret=ret*10+(tmp^'0'),tmp=nc();
	return ret;
}
int n,id,bit[200001];
struct camel{int v[3];}c[200001];
bool cmp(camel X,camel Y){return X.v[id]<Y.v[id];}
inline int query(int X)
{
	int ret=0;
	for(;X<=n;X+=X&-X) ret+=bit[X];
	return ret;
}
inline void update(int X){for(;X;X-=X&-X) bit[X]++;}
long long calc(int X,int Y)
{
	long long ret=0;
	memset(bit,0,sizeof bit);
	sort(c+1,c+n+1,cmp);
	for(int i=1;i<=n;++i)
	{
		ret+=query(c[i].v[Y]);
		update(c[i].v[Y]);
	}
	return ret;
}
int main()
{
	n=RI();
	int i;
	for(i=1;i<=n;++i) c[RI()].v[0]=i;
	for(i=1;i<=n;++i) c[RI()].v[1]=i;
	for(i=1;i<=n;++i) c[RI()].v[2]=i;
	printf("%lld\n",(1ll*n*(n-1)-(calc(id=0,1)+calc(id=1,2)+calc(id=2,0))>>1));
}