D. 按位悖论 详细题解（附标程）

问题简述

• 数组 $a[1..n]$，$b[1..n]$，常数 $v$。
• 区间 $[l,r]$ 是 好区间 当 $(b_l|\dots|b_r) \ge v$。
• 好区间的 优美值 为 $\max(a_l,\dots,a_r)$。
• 操作：单点修改 $b_i$；查询 $[L,R]$ 内所有好区间的最小优美值。
• 约束：$\sum n,\sum q\le 2\cdot10^5$。

核心转化

设 $S = v-1$。则条件 $(b_l|\dots|b_r) \ge v$ 等价于 $(b_l|\dots|b_r) > S$。
在二进制下，$x > S$ 当且仅当存在一个二进制位 $j$，使得 $S$ 的第 $j$ 位为 $0$ 且 $x$ 的第 $j$ 位为 $1$。
因此，好区间等价于：存在某个 $j$ 满足 $(S>>j)\&1 = 0$，且区间内至少有一个 $b$ 在该位为 $1$。

数据结构设计

使用线段树，每个节点维护一个结构体 Info，包含：

• pre[30]：区间内从左往右第一个使该位为 $1$ 的位置（$0$ 表示不存在）。
• suf[30]：区间内从右往左第一个使该位为 $1$ 的位置。
• ans：该区间内所有好区间的最小优美值，若不存在则为 INF。
• l, r：节点区间的左右端点。

叶子节点（位置 $p$）

• 若 $b_p > S$（即 $b_p \ge v$），则单点区间 $[p,p]$ 是好区间，ans = a[p]；否则 ans = INF。
• 对于每个位 $j$，若 $(b_p>>j)\&1 = 1$，则 pre[j]=suf[j]=p，否则为 $0$。

合并操作

合并左节点 $x$ 和右节点 $y$（$x.r+1 = y.l$）得到 $z$。

1. 基础信息：

   • $z.l = x.l$，$z.r = y.r$。
   • $z.ans = \min(x.ans, y.ans)$。
   • 对每个 $j$：
     • $z.pre[j] = x.pre[j] ? x.pre[j] : y.pre[j]$（左边有则用左边，否则用右边）。
     • $z.suf[j] = y.suf[j] ? y.suf[j] : x.suf[j]$（右边有则用右边，否则用左边）。

2. 跨越区间的好区间：
   任何跨越 $x.r$ 和 $y.l$ 的区间形如 $[u, v]$，其中 $u \le x.r$，$v \ge y.l$。我们想找最小的 $\max(a[u..v])$，且存在某个 $j$ 满足 $(S>>j)\&1 = 0$ 且区间内该位为 $1$。
   采用贪心：从中间向两边扩展，按位从高到低处理。
   初始化左边界 $pl = x.r$，右边界 $pr = y.l$。

   对 $j$ 从 $29$ 到 $0$：

   • 在左区间中找 ≤ pl 且第 $j$ 位为 $1$ 的最右位置：u = x.suf[j]，若存在且 $u \le pl$ 则有效，否则视为无效（代码中用 u = min(u, pl) 并结合后续判断处理）。
   • 在右区间中找 ≥ pr 且第 $j$ 位为 $1$ 的最左位置：v = y.pre[j]，若存在且 $v \ge pr$ 则有效，否则视为无效。
   • 计算两个候选区间的最大值（使用 RMQ）：
     • lans = (u ? ds.qry(u, pr) : INF)
     • rans = (v ? ds.qry(pl, v) : INF)
   • 判断 $(S>>j)\&1$：
     • 若为 1：$S$ 的这一位是 $1$ → 这正是我们要找的“自由位”（因为 $S$ 为 $1$ 的位在 $v$ 中为 $0$）。只要区间包含该位，OR 就大于 $S$，从而成为好区间。此时取 $\min(lans, rans)$ 更新 $z.ans$，然后 立即退出循环（高位优先，第一个自由位就能给出最优解）。
     • 若为 0：$S$ 的这一位是 $0$ → $v$ 的这一位是 $1$。该位单独出现不能使 OR > $S$，但我们可以利用它来缩小边界：比较 $lans$ 和 $rans$，选择较小的方向，将边界向内移动（pl = u 或 pr = v），然后继续循环。如果两边都没有有效位置（u 和 v 均为 0），则循环自然结束（无法形成跨越的好区间）。

   循环结束时，$z.ans$ 已经包含了可能的最佳跨越区间的最小优美值。

3. 返回 $z$。

辅助数据结构

• RMQ：对 $a$ 数组建立稀疏表，支持 $O(1)$ 查询区间最大值。因为 $a$ 从不修改。
• 线段树：使用静态数组 seg[N<<2] 预分配节点。建树、更新、查询均为 $O(\log n \cdot 30)$。

查询处理

对于查询 $[L,R]$：

• 全局变量 ansInfo 清空。
• 在线段树中递归查询区间 $[L,R]$，每遇到一个完全覆盖的节点，调用 reply(node.info) 将当前节点信息与 ansInfo 合并（ansInfo = ansInfo + node.info，注意顺序从左到右）。
• 最终答案为 ansInfo.ans，若仍为 INF 则输出 $-1$。

复杂度分析

• 预处理 RMQ：$O(n\log n)$。
• 建树：每个节点 $O(30)$，总 $O(n\cdot 30)$。
• 单次修改：$O(\log n \cdot 30)$。
• 单次查询：访问 $O(\log n)$ 个节点，每个节点合并 $O(30)$，总 $O(\log n \cdot 30)$。
• 总复杂度：$O((n+q)\cdot 30 \cdot \log n)$，在 $2\times10^5$ 范围内可行。

标程代码

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 200000 + 5;   // 题目总和只有 2e5
constexpr int V = 30;
constexpr int INF = INT_MAX;
constexpr int L = 19;

int n, q, S;
int a[N], b[N];

struct RMQ {
    int st[L][N];

    void init() {
        for (int i = 1; i <= n; i++)
            st[0][i] = a[i];

        for (int k = 1; k < L; k++) {
            for (int i = 1; i + (1 << k) - 1 <= n; i++) {
                st[k][i] = max(st[k - 1][i],
                               st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    inline int qry(int l, int r) {
        int k = __lg(r - l + 1);
        return max(st[k][l], st[k][r - (1 << k) + 1]);
    }
} ds;

struct Info {
    int pre[V];
    int suf[V];

    int ans;
    int l, r;

    Info() {
        memset(pre, 0, sizeof(pre));
        memset(suf, 0, sizeof(suf));
        ans = INF;
        l = r = 0;
    }

    inline void clear() {
        memset(pre, 0, sizeof(pre));
        memset(suf, 0, sizeof(suf));
        ans = INF;
        l = r = 0;
    }

    inline void upd(int p) {
        clear();

        l = r = p;

        if (b[p] > S)
            ans = a[p];

        for (int j = 0; j < V; j++) {
            if ((b[p] >> j) & 1) {
                pre[j] = p;
                suf[j] = p;
            }
        }
    }

    friend Info operator + (const Info &x, const Info &y) {
        if (!x.l) return y;
        if (!y.l) return x;

        Info z;

        z.l = x.l;
        z.r = y.r;

        z.ans = min(x.ans, y.ans);

        for (int i = 0; i < V; i++) {
            z.pre[i] = x.pre[i] ? x.pre[i] : y.pre[i];
            z.suf[i] = y.suf[i] ? y.suf[i] : x.suf[i];
        }

        int pl = x.r;
        int pr = y.l;

        for (int i = V - 1; i >= 0; i--) {

            int u = x.suf[i];
            int v = y.pre[i];

            if (u)
                u = min(u, pl);

            if (v)
                v = max(v, pr);

            int lans = u ? ds.qry(u, pr) : INF;
            int rans = v ? ds.qry(pl, v) : INF;

            if (lans < rans) {
                if ((S >> i) & 1) {
                    if (lans < z.ans)
                        pl = u;
                    else
                        break;
                } else {
                    z.ans = min(z.ans, lans);
                }
            } else {
                if ((S >> i) & 1) {
                    if (rans < z.ans)
                        pr = v;
                    else
                        break;
                } else {
                    z.ans = min(z.ans, rans);
                }
            }
        }

        return z;
    }
};

Info ansInfo;

struct Node {
    int l, r, mid;

    Node *ls, *rs;

    Info info;
};

Node seg[N << 2];
int tot;

Node* build(int l, int r) {

    Node *u = &seg[++tot];

    u->l = l;
    u->r = r;
    u->mid = (l + r) >> 1;

    if (l == r) {
        u->info.upd(l);
        return u;
    }

    u->ls = build(l, u->mid);
    u->rs = build(u->mid + 1, r);

    u->info = u->ls->info + u->rs->info;

    return u;
}

inline void pushup(Node *u) {
    u->info = u->ls->info + u->rs->info;
}

void update(Node *u, int p) {

    if (u->l == u->r) {
        u->info.upd(p);
        return;
    }

    if (p <= u->mid)
        update(u->ls, p);
    else
        update(u->rs, p);

    pushup(u);
}

inline void reply(const Info &x) {
    ansInfo = ansInfo + x;
}

void query(Node *u, int l, int r) {

    if (u->l >= l && u->r <= r) {
        reply(u->info);
        return;
    }

    if (l <= u->mid)
        query(u->ls, l, r);

    if (r > u->mid)
        query(u->rs, l, r);
}

void solve() {

    cin >> n >> S;
    S--;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    ds.init();

    for (int i = 1; i <= n; i++)
        cin >> b[i];

    tot = 0;
    Node *rt = build(1, n);

    cin >> q;

    while (q--) {

        int op;
        cin >> op;

        if (op == 1) {

            int p, x;
            cin >> p >> x;

            b[p] = x;

            update(rt, p);

        } else {

            int l, r;
            cin >> l >> r;

            ansInfo.clear();

            query(rt, l, r);

            cout << (ansInfo.ans == INF ? -1 : ansInfo.ans) << ' ';
        }
    }

    cout << '\n';
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

总结

本题的核心是利用 $S=v-1$ 将条件转化为“存在一个 $S$ 中为 $0$ 的位在区间 OR 中为 $1$”，然后通过线段树维护每个位的最左最右出现位置，在合并时采用高位优先的贪心策略，逐步收缩边界并更新答案。标程实现了这一算法，可以高效处理在线修改和区间查询。