Description：

给你三个数列 $\{a_i\},\{b_i\},\{c_i\}$ ，保证每个数列都恰好是一个排列。你需要求出满足 $a_i<a_j,b_i<b_j,c_i<c_j$ 的有序对 $(i,j)$ 的数目。

$1\leqslant n\leqslant 2\times 10^6$

Solution：

如果 $n\leqslant10^5$ 那么就是一个 $CDQ$ 分治裸题了，但是这题保证每个数都是一个排列，也就是说两两不同，正解是计算以下三个东西： $$ X=\sum_{i,j}[a_i<a_j][b_i<b_j]\\ Y=\sum_{i,j}[b_i<b_j][c_i<c_j]\\ Z=\sum_{i,j}[c_i<c_j][a_i<a_j]\\ $$ 由于不存在相同的数，所以一个会对答案有贡献的 $(i,j)$ 在三个中都出现过，其他的只会在一个中出现，于是有： $$ ans=\frac 1 2(X+Y+Z-{n\choose 2}) $$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

const int N = 2e6+1;

unsigned int SA,SB,SC;

int n,a[N],b[N],c[N];

int w[N],g[N];

long long ans = 0;

inline void calc(int a[],int b[])

{

	for(register int i = 1;i <= n;++i)

	{

		*(g + *(a + i)) = i;

		*(w + i) = 0;

	}

	for(register int k = 1;k <= n;++k)

	{

		for(register int i = *(b + *(g + k));i >= 1;i -= i & (-i))ans += *(w + i);

		for(register int i = *(b + *(g + k));i <= n;i += i & (-i))++*(w + i);

	}

	return;

}

int main(){

	freopen("cdq.in","r",stdin);

	freopen("cdq.out","w",stdout);

	scanf("%d%u%u%u",&n,&SA,&SB,&SC);

	for(register int i = 1;i <= n;++i)*(a + i) = *(b + i) = *(c + i) = i;

	register unsigned int t;

	for(register int i = 1;i <= n;++i)

	{

		SA ^= SA << 16;SA ^= SA >> 5;SA ^= SA << 1;

		t = SA;SA = SB;SB = SC;SC ^= t ^ SA;

		swap(*(a + i),*(a + 1 + SC % n));

	}

	for(register int i = 1;i <= n;++i)

	{

		SA ^= SA << 16;SA ^= SA >> 5;SA ^= SA << 1;

		t = SA;SA = SB;SB = SC;SC ^= t ^ SA;

		swap(*(b + i),*(b + 1 + SC % n));

	}

	for(register int i = 1;i <= n;++i)

	{

		SA ^= SA << 16;SA ^= SA >> 5;SA ^= SA << 1;

		t = SA;SA = SB;SB = SC;SC ^= t ^ SA;

		swap(*(c + i),*(c + 1 + SC % n));

	}

	calc(a,b);calc(b,c);calc(a,c);

	printf("%lld\n",(ans - 1ll * n * (n - 1) / 2) >> 1);

	fclose(stdin);

	fclose(stdout);

	return 0;

}