luogu.p6025.md

线段树 | 数论分块 - TueNov19 2024

Luogu P6025 设 $f(n)$ 是在 $[1, n]$ 建线段树后节点最大下标。求: $$f(i)\oplus f(i+1)\oplus\cdots\oplus f(j)$$ $\oplus$ 是异或。$1\le i\le j\le10^{15}$. 建树细节见下面代码：

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);

观察实现细节：

• 下标从 1 开始。
• 左节点 $2u$，右节点 $2u+1$。
• 如果长度 $n$ 是偶数，区间对半分；如果是奇数，左边比右边多 1。

由于我们只考虑下标，上面的代码可以这样写减少参数。函数意思是：以 $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}$，可以直接处理。端点： $$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';
}