记录编号	423487	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[郑州集训 2017]NOI模拟题5.1	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	13.263 s
提交时间	2017-07-11 23:56:09	内存使用	53.72 MiB

#include  <iostream>
#include <algorithm>
#include    <cstdio>
#include   <cstring>
using namespace std;
const int MAXN = 2e6 + 10;
int lastInt, seed;
inline int nextInt() {
	static const int mod = 1e9 + 7;
	lastInt = lastInt ^ (((long long)lastInt * lastInt + seed) % mod);
	return lastInt;
}
void getPerm(int P[], int n, int x0, int c) {
	for (int i = 1; i <= n; ++i) P[i] = i;
	lastInt = x0;
	seed = c;
	for (int i = n; i >= 1; --i) std::swap(P[i], P[nextInt() % i + 1]);
}
int A[MAXN], B[MAXN], C[MAXN];
void gen_data(int n, int a0, int seed_a, int b0, int seed_b, int c0, int seed_c) {
	getPerm(A, n, a0, seed_a);
	getPerm(B, n, b0, seed_b);
	getPerm(C, n, c0, seed_c);
}
int n;
struct Data {
	int a, b, c;
}a[MAXN];
int c[MAXN];
inline int lowbit(int x) { return x&-x; }
inline void Add(int p, int v) { while (p <= n)c[p] += v, p += lowbit(p); }
inline int Sum(int p) {
	int temp = 0;
	while (p)temp += c[p], p -= lowbit(p);
	return temp;
}
bool cmp1(Data x, Data y) { return x.a < y.a; }
bool cmp2(Data x, Data y) { return x.b < y.b; }
long long ans = 0;
int main(){
	freopen("order1.in", "r", stdin);
	freopen("order1.out", "w", stdout);
	int a0, s_a,b0, s_b,c0, s_c;
	std::cin >> n;
	std::cin >> a0 >> s_a;
	std::cin >> b0 >> s_b;
	std::cin >> c0 >> s_c;
	gen_data(n, a0, s_a, b0, s_b, c0, s_c);
	for (int i = 1;i <= n;i++) {
		a[i].a = A[i], a[i].b = B[i], a[i].c = C[i];
	}
	ans = (long long)n*(n - 1);
	sort(a + 1, a + n + 1, cmp1);
	for (int i = 1;i <= n;i++) { Add(a[i].b, 1), ans -= (i - Sum(a[i].b)); }
	memset(c, 0, sizeof(c));
	for (int i = 1;i <= n;i++) { Add(a[i].c, 1), ans -= (i - Sum(a[i].c)); }
	sort(a + 1, a + n + 1, cmp2);
	memset(c, 0, sizeof(c));
	for (int i = 1;i <= n;i++) { Add(a[i].c, 1), ans -= (i - Sum(a[i].c)); }
	printf("%lld", ans>>1);
	fclose(stdin);
	fclose(stdout);
	return 0;
}