题解

这道题要求我们找到一个最小的 $b$，使得对数组进行异或变换后，数组变为非递减序列。我们需要在初始状态和每次单点修改后输出答案。

问题转化

首先，我们分析条件：

$$(a[i] \oplus b) \leq (a[i+1] \oplus b) \quad \text{对所有} \ i=1,\dots,n-1 $$

对于每对相邻元素 $(a[i], a[i+1])$，我们需要找到满足条件的 $b$。最终答案需要满足所有相邻对的约束。

按位分析

考虑两个数 $x$ 和 $y$（$x = a[i], y = a[i+1]$），我们想知道 $b$ 应该满足什么条件才能使得 $x \oplus b \leq y \oplus b$。

设 $k = \text{msb}(x \oplus y)$，即 $x$ 和 $y$ 的最高不同位。由于 $k$ 是最高不同位，我们可以得到：

对于 $x \oplus b$ 和 $y \oplus b$ 的比较，关键是看第 $k$ 位：

• 如果 $x$ 的第 $k$ 位为 0，$y$ 的第 $k$ 位为 1，那么无论 $b$ 的第 $k$ 位是什么，$x \oplus b$ 的第 $k$ 位都会小于等于 $y \oplus b$ 的第 $k$ 位，且高位相同
  • 如果 $b_k = 0$，则 $(x \oplus b)_k = 0$，$(y \oplus b)_k = 1$
  • 如果 $b_k = 1$，则 $(x \oplus b)_k = 1$，$(y \oplus b)_k = 0$
• 如果 $x$ 的第 $k$ 位为 1，$y$ 的第 $k$ 位为 0，情况类似

更精确地说：

1. 如果 $x < y$：

   • 设 $k = \text{msb}(x \oplus y)$
   • 如果 $x$ 的第 $k$ 位为 0，$y$ 的第 $k$ 位为 1
     • 那么需要 $b$ 的第 $k$ 位为 0（否则会反转大小关系）
   • 如果 $x$ 的第 $k$ 位为 1，$y$ 的第 $k$ 位为 0
     • 那么需要 $b$ 的第 $k$ 位为 1（否则会反转大小关系）

2. 如果 $x > y$：

   • 设 $k = \text{msb}(x \oplus y)$
   • 如果 $x$ 的第 $k$ 位为 0，$y$ 的第 $k$ 位为 1
     • 那么需要 $b$ 的第 $k$ 位为 1（这样才能使 $x \oplus b > y \oplus b$）
   • 如果 $x$ 的第 $k$ 位为 1，$y$ 的第 $k$ 位为 0
     • 那么需要 $b$ 的第 $k$ 位为 0（这样才能使 $x \oplus b > y \oplus b$）

简化结论

实际上，我们可以用更简洁的方式描述：

对于相邻元素 $a[i]$ 和 $a[i+1]$：

• 如果 $a[i] < a[i+1]$：

  • 设 $k = \text{msb}(a[i] \oplus a[i+1])$
  • 如果 $a[i]$ 的第 $k$ 位为 0，则 $b$ 的第 $k$ 位必须为 0
  • 如果 $a[i]$ 的第 $k$ 位为 1，则 $b$ 的第 $k$ 位必须为 1

  等价于：$b$ 的第 $k$ 位必须等于 $a[i]$ 的第 $k$ 位。

• 如果 $a[i] > a[i+1]$：

  • 设 $k = \text{msb}(a[i] \oplus a[i+1])$
  • 如果 $a[i]$ 的第 $k$ 位为 0，则 $b$ 的第 $k$ 位必须为 1
  • 如果 $a[i]$ 的第 $k$ 位为 1，则 $b$ 的第 $k$ 位必须为 0

  等价于：$b$ 的第 $k$ 位必须等于 $1 - a[i]$ 的第 $k$ 位（即 $a[i]$ 的第 $k$ 位取反）。

• 如果 $a[i] = a[i+1]$：对 $b$ 没有约束。

算法设计

根据上述分析，我们可以为每个二进制位 $k$ 维护两个计数器：

• cnt_nd[k]：第 $k$ 位必须为 1 的约束数量
• cnt_ban[k]：第 $k$ 位必须为 0 的约束数量

初始构建

遍历所有相邻对 $(a[i], a[i+1])$：

• 如果 $a[i] < a[i+1]$：
  • 设 $k = \text{msb}(a[i] \oplus a[i+1])$
  • 如果 $(a[i] >> k) \& 1 = 1$，则 cnt_nd[k]++（该位必须为 1）
  • 如果 $(a[i] >> k) \& 1 = 0$，则 cnt_ban[k]++（该位必须为 0）
• 如果 $a[i] > a[i+1]$：
  • 设 $k = \text{msb}(a[i] \oplus a[i+1])$
  • 如果 $(a[i] >> k) \& 1 = 1$，则 cnt_ban[k]++（该位必须为 0）
  • 如果 $(a[i] >> k) \& 1 = 0$，则 cnt_nd[k]++（该位必须为 1）
• 如果 $a[i] = a[i+1]$：不操作

查询答案

要找到最小的 $b$，我们从高位到低位贪心地确定每一位：

1. 如果某一位同时存在必须为 1 和必须为 0 的约束（即 cnt_nd[k] > 0 且 cnt_ban[k] > 0），则无解，返回 -1
2. 否则：
   • 如果存在必须为 1 的约束（cnt_nd[k] > 0），则该位必须为 1
   • 否则（cnt_nd[k] = 0）：
     • 如果存在必须为 0 的约束（cnt_ban[k] > 0），则该位必须为 0
     • 否则，为了得到最小的 $b$，该位设为 0

注意：由于我们是从高位到低位确定，且在没有约束时设该位为 0，这样得到的就是最小的满足条件的 $b$。

修改操作

当修改位置 $u$ 的值时，只有与 $u$ 相关的相邻对会发生变化：

• $(a[u-1], a[u])$（如果 $u > 1$）
• $(a[u], a[u+1])$（如果 $u < n$）

我们需要：

1. 移除旧值对应的约束
2. 添加新值对应的约束
3. 更新数组 $a$ 的值

复杂度分析

• 初始构建：$O(n \log M)$，其中 $M$ 是数值范围（$2^{30}$）
• 每次查询：$O(\log M)$
• 每次修改：$O(\log M)$
• 总复杂度：$O((n+q) \log M)$

对于 $n, q \leq 10^6$，$\log M = 30$，可以在时限内完成。

正确性证明

1. 必要性：如果 $b$ 是所有约束的解，那么它必须满足每个约束条件。
2. 充分性：如果 $b$ 满足所有约束条件，那么对于任意相邻对 $(a[i], a[i+1])$，考虑最高不同位 $k$，$b$ 的第 $k$ 位确保了 $a[i] \oplus b$ 和 $a[i+1] \oplus b$ 的大小关系正确。
3. 最小性：我们从高位到低位贪心地确定 $b$，在没有约束时设为 0，这保证了得到的 $b$ 是最小的。

代码实现细节

// 检查相邻对并更新约束
void chk(int a, int b) {
    if (a == b) return;
    int k = std::__lg(a ^ b);  // 求最高不同位
    
    if (a < b) {
        // a的第k位决定b的第k位
        if ((a >> k) & 1) cnt_nd[k]++;  // 必须为1
        else cnt_ban[k]++;  // 必须为0
    } else { // a > b
        // a的第k位取反决定b的第k位
        if ((a >> k) & 1) cnt_ban[k]++;  // 必须为0
        else cnt_nd[k]++;  // 必须为1
    }
}

// 移除约束
void unchk(int a, int b) {
    if (a == b) return;
    int k = std::__lg(a ^ b);
    
    if (a < b) {
        if ((a >> k) & 1) cnt_nd[k]--;
        else cnt_ban[k]--;
    } else {
        if ((a >> k) & 1) cnt_ban[k]--;
        else cnt_nd[k]--;
    }
}

// 查询答案
int get_ans() {
    int ans = 0;
    for (int i = 30; i >= 0; i--) {
        if (cnt_nd[i] && cnt_ban[i]) return -1;  // 冲突
        if (cnt_nd[i]) ans |= (1 << i);  // 必须为1
        // 否则：要么必须为0，要么无约束，都设为0以保证最小
    }
    return ans;
}

总结

本题的关键在于将相邻元素的大小关系约束转化为对 $b$ 的二进制位的约束。通过维护每个二进制位的约束计数器，我们可以在 $O(\log M)$ 的时间内回答查询，并支持 $O(\log M)$ 的单点修改。这是一个典型的位运算+约束满足问题，通过巧妙的位分析简化了问题。