P14302 基础倍增练习题 6 / 小 U 的树
题目描述
给定 $n$ 个点，点有权，初始时两两均未连边。
你需要支持 $m$ 次两种操作之一：
1. 在两个不联通的点间连上一条边；
2. 求两个给定点构成路径上所有点权的最大子段和（不能为空）。
强制在线。
输入格式
由于输入量较大，本题数据采用程序内随机生成的方式。
第一行三个正整数 $n,m,sd$，其中 $sd\in[0,2^{64})$ 为六十四位无符号整数。你需要将 $sd$ 重赋值为对其调用 `splitmix64` 得到的值。随后你需要调用 $n$ 次 `rnd()` 生成每个点的点权，在有符号三十二位整数范围内。
随后你需要生成 $m$ 次操作。每次操作调用两次 `rnd()` 模 $n$ 的值加一以生成两个随机点，随后若其不联通则执行操作 1，否则执行操作 2。
关于更多细节，见提示说明部分。
**上述数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。**
输出格式
对于每次 2 操作，将答案异或给 $sd$。在程序的最后，一行输出 $sd$ 即可。
关于更多细节，见提示说明部分。
说明/提示
对于 $10\%$ 的数据，$n,m\le 10^3$；
对于 $20\%$ 的数据，$n,m\le 10^4$；
对于 $30\%$ 的数据，$n,m\le 10^5$；
对于 $50\%$ 的数据，$n,m\le5\times10^5$；
对于 $70\%$ 的数据，$n,m\le 10^6$；
对于 $100\%$ 的数据，$1\le n,m\le 3\times10^6$，$0\le sd\lt2^{64}$。
---
以下是部分样板代码。
随机数部分：
```cpp
uint64_t sd;
uint64_t rnd() {
sd ^= sd > 7;
return sd ^= sd > 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
```
主函数部分：
```cpp
cin >> n >> m >> sd, sd = splitmix64(sd);
for (int i = 1; i