线段树 | 数论分块 - TueNov19 2024

· · 题解

设 f(n) 是在 [1, n] 建线段树后节点最大下标。求:

f(i)\oplus f(i+1)\oplus\cdots\oplus f(j) ```cpp using ll = long long; void init(ll u, ll ul, ll ur) { if (ul == ur) return; ll um = (ul + ur) / 2; init(u*2, ul, um); init(u*2+1, um+1, ur); } // f(1, 1, n); ```

观察实现细节：

由于我们只考虑下标，上面的代码可以这样写减少参数。函数意思是：以 u 位根节点建长度为 n 的线段树，返回最大节点下标。时间 O(n)。

ll f1(ll n, ll u) {
  if (n == 1) return u;
  if (n&1) return std::max(
    f1(n/2+1, u*2), f1(n/2, u*2+1)
  );
  return f(n/2, u*2+1)
} // f(n, 1)

时间瓶颈在于当 n 是奇数时，不好决定选哪棵子树。模拟 n\in[8,16] 的区间，比较树的形态变化过程，可以发现，左比右更优的唯一可能是 n-1 时建了一颗满二叉树。变化到 n 时，要用新的一层，而这新的一层刚好只有 2 个节点，它们的父节点是上一层的最左边的节点。答案是这 2 个节点中靠右的一部分。所以，当 n=2^t+1(t\ge1) 时选左子树，其它时候选右子树。

判断 t 是否存在可以这样做。证明也附上。

(n & n-2) == 1 && n != 1

我们实际上是想判定 n 二进制表示是这种形式

1\underbrace{00\cdots0}_{t-1(\ge0)\ 个\ 0}1

可以验证存在 t 的 n 一定满足这个表达式。按照位与，n 的低位一定是 1。减 2 刚好会让第二位到第 w 位都取反，其中 w 是第 2 位起往高位第一个 1。这 (w-1) 位一定会变化。从结果看，更高位一定是 0，所以满足上面语句的 n 的二进制表示一定是上面那样。

现在我们可以在 O(\log n) 内求出 f 了：

ll f(ll n, ll u) {
  if (n == 1) return u;
  if ((n & (n - 2)) == 1)
    return f(n / 2 + 1, u * 2);
  return f(n / 2, u * 2 + 1);
}

还能进一步优化。上面这种特殊情况可以直接写出答案：

f(n)=f(2^t+1)=2^{t+1}+1=2n-1

所以选左子树时的答案可以常数求出来。实现时注意一个细节，在 f(n, u) 的结构里，根节点不一定是 1。这不能优化最坏时间，这种代码我就不写了。

接着考虑区间异或，转换成 [1, i-1] 和 [1, j] 的答案之异或。模拟 [8,16] 会发现这就是在往第 5 层逐渐添叶子，一下添根节点的左子树，一下右节点。同一层里，先加右边，再加左边时答案不变，这两个异或是 0。所以对于这种连续区间 [2^k+1, 2^{k+1}](k\ge1)，可以直接处理。端点：

f(2^k+1)=2^{k+1}+1\quad f(2^{k+1})=2^{k+2}-1

通过打表可以验证这一结论。

实现上，设 k\ge1 表示最后一个完整区间，如果 k 不存在就是边界 n\le3。

if (n <= 3) return v[n];

让 k 是 2^{k+1}\le n 下 k 的最大值，循环时保持 p=2^{k+2}：

ll k = 1;
for (ll p = 8; p <= n; p <<= 1) k++;

处理连续的区间 [2^i+1, 2^{i+1}](1\le i\le k)，循环中保持 p=2^{i+1}，端点的函数值为：

f(2^i+1)=2^{i+1}+1=p+1\qquad f(2^{i+1})=2^{i+2}-1=2p-1 
ll a = v[2];  // 注意第一个区间 [3, 4] 前面的边界
for (ll p = 4, i = 1; i <= k; i++, p<<=1)
  a ^= ((p + 1) ^ (2 * p - 1));

对于多出来的情况，设最后一个区间右端点是 2^{k+1}=q：

// 不要把 1ll 写成 1，给 int 左移不会扩充成 long long
ll q = 1ll << (k + 1);

如果有多的（n>q），先把下一个区间左端点处理了：

f(q+1)=f(2^{k+1}+1)=2^{k+2}+1=2q+1 
if (n > q) a ^= 2 * q + 1;

在相同的两个数对（偶，奇）里，如果 n 是第一个，就要另外算上：

if (n > q + 1 && !(n & 1)) a ^= f(n, 1);

这道题就做完了。

Code

#include <iostream>
using ll = long long;
ll v[]{0, 1, 3, 5};

ll f(ll n, ll u) {
  if (n == 1) return u;
  if ((n & (n - 2)) == 1)
    return f(n / 2 + 1, u * 2);
  return f(n / 2, u * 2 + 1);
}

ll g(ll n) {
  if (n <= 3) return v[n];
  ll a = v[2], k = 1;
  for (ll p = 8; p <= n; p <<= 1) k++;
  for (ll p = 4, i = 1; i <= k; i++, p<<=1)
    a ^= ((p + 1) ^ (2 * p - 1));
  ll q = 1ll << (k + 1);
  if (n > q) a ^= 2 * q + 1;
  if (n > q + 1 && !(n & 1))
    a ^= f(n, 1);
  return a;
}

int main() {
  v[2] ^= v[1], v[3] ^= v[2];
  ll lf, rg; std::cin >> lf >> rg;
  std::cout << (g(rg) ^ g(lf - 1)) << '\n';
}