题目描述

给定 $n$ 个点，点有权，初始时两两均未连边。

你需要支持 $m$ 次两种操作之一：

1. 在两个不联通的点间连上一条边；

2. 求两个给定点构成路径上所有点权的最大子段和（不能为空）。

强制在线。

输入格式

由于输入量较大，本题数据采用程序内随机生成的方式。

第一行三个正整数 $n,m,sd$，其中 $sd\in[0,2^{64})$ 为六十四位无符号整数。你需要将 $sd$ 重赋值为对其调用 splitmix64 得到的值。随后你需要调用 $n$ 次 rnd() 生成每个点的点权，在有符号三十二位整数范围内。

随后你需要生成 $m$ 次操作。每次操作调用两次 rnd() 模 $n$ 的值加一以生成两个随机点，随后若其不联通则执行操作 1，否则执行操作 2。

关于更多细节，见提示说明部分。

输出格式

对于每次 2 操作，将答案异或给 $sd$。在程序的最后，一行输出 $sd$ 即可。

关于更多细节，见提示说明部分。

3 3 114514

17246579553375009221

10 10 114514

4275621686360879090

100000 100000 114514

12109274478506447081

提示

对于 $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}$。

---

以下是部分样板代码。

随机数部分：

uint64_t sd;
uint64_t rnd() {
  sd ^= sd << 13, sd ^= sd >> 7;
  return sd ^= sd << 17;
}
uint64_t splitmix64(uint64_t x) {
  x += 0x9e3779b97f4a7c15;
  x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  return x ^ (x >> 31);
}

主函数部分：

  cin >> n >> m >> sd, sd = splitmix64(sd);
  for (int i = 1; i <= n; ++i) a[i] = (uint32_t)rnd();
  // 假设 a 为点权数组，注意其类型为 int。
  while (m--) {
    int u = rnd() % n + 1, v = rnd() % n + 1;
    if (is_connected(u, v))
      sd ^= query(u, v);
    else
      unite(u, v);
    // 假设三个函数的功能分别为：判断是否联通；查询最大子段和；连边。
  }
  cout << sd << endl;

---

如果你 T 了，可以考虑减少瓶颈复杂度的出现次数。