题目描述

测试你的离散化。

有一组 $n$ 个数的数列，若有相同的数则只计算一次。

有 $n$ 个询问，每个询问查询第 $i$ 个数在原数列中是第几大的数。若有相同的数则只计算一次。

使用数据生成器生成读入，提供模板：

const int N = 1e7 + 10;
typedef unsigned ul;
ul seed, a[N], ans = 0;
inline void rand(ul &r) {
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	r = seed;
}
#define calc(i, x) ((((i) - (x)) << 13) ^ (((i) + (x)) >> 17) ^ ((i) << 5))

int main() {
    int n; scanf("%d%u", &n, &seed);
    for (int i = 1; i <= n; i++) rand(a[i]);
    for (int i = 1; i <= n; i++) {
        ul q, r; rand(q); q = q % n + 1;
        // get r: rank of a[q] ...
        ans ^= calc(i, r);
    }
    printf("%u\n", ans);
    return 0;
}

输入格式

一行三个整数 $n, seed_1,seed_2$。

满足 $seed_1,seed_2\in[0, 2^{32})$。

输出格式

输出一个答案，为每个询问答案的异或和。

样例 #1

样例输入 #1

10 5

样例输出 #1

24928

提示

对于所有数据满足 $n\in[1, 10^7]$。

对于编号为 $i$ 的数据，满足 $n = \lfloor10^{i / 2}\rfloor$

• gen.py

from cyaron import *

for _ in range(1, 15):
    f = IO(file_prefix="d", data_id=_)
    n = int(10 ** (_ / 2))
    seed = randint(1, 2 ** 32 - 1)
    f.input_writeln(n, seed)
    f.output_gen("hash.exe")