A7444 | 攀登

你们居然挺过来了，真是令人难以置信，不是吗？

努力的过程还是挺有意思的。

答应我，一定要照顾好自己，好吗？

> ——《蔚蓝》第七章 C 面

请注意本题特殊的时间限制。

有 $n$ 个数，编号从 $1$ 到 $n$，编号为 $i$ 的数初始值为 $a_i$。最开始，每个数单独在一个可重集中。有 $q$ 次操作，每次操作有三种类型：

* 「和解」void merge(int x, int y)：将编号为 $x$ 的数所在的可重集与编号 $y$ 的数所在的可重集合并。若两个数本来就在一个可重集中，不进行操作；
* 「坠落」void update(int x, int v)：将编号为 $x$ 的数所在的可重集中的每一个数 $p$ 变为 $\lfloor\sqrt{|p-v|}\rfloor$，保证 $v\in\{0,1\}$；
* 「挑战」long long query(int x)：返回编号为 $x$ 的数所在的可重集中每一个数的和。

为了避免过多的输入输出，你只需要在给出的代码模板的基础上实现 merge、update 和 query 这三个函数。具体地，代码模板会先生成 $c,n,q$ 和 $a_i$，并分别存储在变量 c、n、q 和 a[i] 中，其中 $c$ 为测试点编号，然后调用 init 函数供你初始化你创建的全局变量，最后调用 $q$ 次 merge、update 或 query 三个函数并判断 query 函数的返回值是否正确。注意你需要使用不低于 C++11 的 C++ 版本编译代码模板。

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 10001000;
int c, n, q, a[N]; // 你可以在这里创建全局变量
void init() {
// 你可以在这里进行初始化
}
void merge(int x, int y) {
// 在这里实现 merge 函数
}
void update(int x, int v) {
// 在这里实现 update 函数
}
long long query(int x) {
// 在这里实现 query 函数
}

int main() {
unsigned long long seed, ans = 0;
cin >> c >> n >> q >> seed;
auto rnd = [&]() -> unsigned int {
seed += 0x9e3779b97f4a7c15ull;
unsigned long long z = seed;
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ull;
z = (z ^ (z >> 27)) * 0x94d049bb133111ebull;
return (z ^ (z >> 31));
};
for (int i = 1; i <= n; i++) {
if (c == 5 || c == 6) a[i] = rnd() % 2;
else a[i] = rnd() % 1000000001;
}
init();
for (int i = 1; i <= q; i++) {
int op = rnd() % 3;
if (op == 0) merge(rnd() % n + 1, rnd() % n + 1);
if (op == 1) update(rnd() % n + 1, (c == 7 || c == 8) ? 1 : rnd() % 2);
if (op == 2) ans += query(rnd() % n + 1);
}
cout << ans;
return 0;
}

你不需要，也不应该输入任何内容，并保持代码模板中 main 函数的内容不变。

你不需要，也不应该输出任何内容，并保持代码模板中 main 函数的内容不变。