记录编号	423471	评测结果	AAAAAAATTTTAAAATTTTT
题目名称	2729.[郑州集训 2017]NOI模拟题5.1	最终得分	55
用户昵称	AAAAAAAAAA	是否通过	未通过
代码语言	C++	运行时间	19.687 s
提交时间	2017-07-11 22:09:08	内存使用	152.90 MiB

#include  <iostream>
#include <algorithm>
#include    <cstdio>
using namespace std;
const int MAXN = 4e6 + 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], t[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 cmp(Data x, Data y) { return (x.a == y.a&&x.b == y.b) ? x.c < y.c : (x.a == y.a ? x.b < y.b : x.a < y.a); }
long long ans = 0;
void CDQ(int l, int r) {
	if (l == r)return;
	int mid = (l + r) >> 1;
	CDQ(l, mid);CDQ(mid + 1, r);
	int i = l, p = l, j = mid + 1;
	while (i <= mid || j <= r) {
		if (j>r || (i <= mid&&a[i].b <= a[j].b))add(a[i].c, 1), t[p++] = a[i++];
		else ans += sum(a[j].c), t[p++] = a[j++];
	}
	for (int i = l;i <= mid;i++)add(a[i].c, -1);
	for (int i = l;i <= r;i++)a[i] = t[i];
}
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];
	sort(a + 1, a + n + 1, cmp);
	CDQ(1, n);
	printf("%lld", ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}