A128498.攀登

你们居然挺过来了，真是令人难以置信，不是吗？
努力的过程还是挺有意思的。
答应我，一定要照顾好自己，好吗？

——《蔚蓝》第七章 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 函数的返回值是否正确。注意你需要使用不低于 C11 的 C 版本编译代码模板。

#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 函数的内容不变。

【样例解释】

你可以将代码的 main 函数替换为以下片段以测试代码能否通过样例：

int main() {
    c = 0, n = 5, q = 12;
    for (int i = 1; i <= n; i++)
        a[i] = i + 5;
    init();
    merge(1, 5), update(5, 1);
    cout << query(1) << endl;
    merge(4, 5), update(4, 1);
    cout << query(4) << endl;
    merge(2, 1), update(1, 0);
    cout << query(5) << endl;
    update(2, 1);
    cout << query(2) << endl;
    cout << query(3) << endl; 
    return 0;
}

• 初始时，$a_1=6$，$a_2=7$，$a_3=8$，$a_4=9$，$a_5=10$。
• 进行操作 update(5, 1) 后，编号为 $5$ 的数所在的可重集由 $\{6,10\}$ 变为 $\{2,3\}$，操作 query(1) 答案为 $5$；
• 进行操作 update(4, 1) 后，编号为 $4$ 的数所在的可重集由 $\{2,3,9\}$ 变为 $\{1,1,2\}$，操作 query(4) 答案为 $4$；
• 进行操作 update(1, 0) 后，编号为 $1$ 的数所在的可重集由 $\{1,1,2,7\}$ 变为 $\{1,1,1,2\}$，操作 query(5) 答案为 $5$；
• 进行操作 update(2, 1) 后，编号为 $1$ 的数所在的可重集由 $\{1,1,1,2\}$ 变为 $\{0,0,0,1\}$，操作 query(2) 答案为 $1$；
• 编号为 $3$ 的数没有被操作过，操作 query(3) 答案为 $8$。

【数据范围】

测试点编号	特殊性质
$1-2$	$n,q\le5\times10^3$
$3-4$	$n,q\le10^6$
$5-6$	$a_i\le1$
$7-8$	$v=1$
$9-10$	无

对于 $100\%$ 的测试数据，保证：$1\le n\le10^7$，$1\le q\le 2\times10^7$，$0\le a_i\le10^9$，$1\le x,y\le n$，$v\in\{0,1\}$。