异或运算

GitHub跳转原题关系图返回列表

把二维第 k 大按最高位贪心拆成逐位计数,用可持久化 01-Trie 上的前缀版本差得到区间按位个数,n 个 X 的指针整排一起下钻。

OJ: roj

题目 ID: 1702

难度:提高+/省选-

标签:可持久化Trie位运算二进制python

创建: 2026-10-07 16:01

更新: 2026-10-07 16:01

形式化题目

给定两个非负整数数列

X={x1,x2,…,xn},Y={y1,y2,…,ym},X = \{x_1, x_2, \dots, x_n\}, \qquad Y = \{y_1, y_2, \dots, y_m\},

构造 n×mn \times m 的矩阵 AA,其中 Aij=xi⊕yjA_{ij} = x_i \oplus y_j(⊕\oplus 表示按位异或)。 下述 pp 次询问互相独立,每次给出 u,d,l,r,ku, d, l, r, k,要求输出子矩形

{ Aij  ∣  u⩽i⩽d,  l⩽j⩽r }\{\, A_{ij} \;\big|\; u \leqslant i \leqslant d,\; l \leqslant j \leqslant r \,\}

中第 kk 大的元素值(kk 从 11 开始计数,即 k=1k = 1 求最大值)。

数据规模:0⩽xi,yj<2310 \leqslant x_i, y_j < 2^{31},1⩽n⩽10001 \leqslant n \leqslant 1000,1⩽m⩽3000001 \leqslant m \leqslant 300000, 1⩽k⩽(d−u+1)(r−l+1)1 \leqslant k \leqslant (d-u+1)(r-l+1),1⩽p⩽5001 \leqslant p \leqslant 500。

以题目样例为例,X=(1,2,4)X = (1,2,4)、Y=(7,6,5)Y = (7,6,5) 时矩阵为

AijA_{ij} y1=7y_1 = 7 y2=6y_2 = 6 y3=5y_3 = 5
x1=1x_1 = 1 6 7 4
x2=2x_2 = 2 5 4 7
x3=4x_3 = 4 3 2 1

第一次询问取 i∈[1,2]i \in [1,2]、j∈[1,2]j \in [1,2] 的四个数 6,7,5,46, 7, 5, 4,第 2 大为 66; 第二次取 i∈[1,2]i \in [1,2]、j∈[1,3]j \in [1,3] 的六个数,第 4 大为 55。

正解

思路

先看朴素做法。 每次询问把子矩形里的 (d−u+1)(r−l+1)(d-u+1)(r-l+1) 个数全部枚举出来排序, 取第 kk 个。单次代价已经高达 n×m=3×108n \times m = 3 \times 10^8 量级,pp 次询问完全不可行。 就算把排序换成桶,也还是绕不开"枚举整个子矩形"这一步。

关键观察一:第 kk 大可以逐位确定,不需要排序。 把所有值看成定长的二进制串, “第 kk 大"就是"按字典序(高位优先)第 kk 大”。于是可以把候选集合按最高位劈成两半:

  • 若最高位为 11 的元素有 cnt1\mathrm{cnt}_1 个,且 k⩽cnt1k \leqslant \mathrm{cnt}_1, 则答案的最高位是 11,且第 kk 大落在"最高位为 1"这一半里;
  • 否则答案最高位是 00,并把 kk 减去 cnt1\mathrm{cnt}_1——那一半已经被整块跳过了。

确定一位后,候选集合收缩到对应的那一半,再对次高位做同样的事。 重复 31 次就得到完整答案。排序被换成了 31 次"某一半有多少个"的计数。

关键观察二:二维的位计数能拆成一维的按位计数。 对固定的 ii 和位 bb,

Aij 的第 b 位=xi 的第 b 位⊕yj 的第 b 位,A_{ij} \text{ 的第 } b \text{ 位} = x_i \text{ 的第 } b \text{ 位} \oplus y_j \text{ 的第 } b \text{ 位},

所以 AijA_{ij} 第 bb 位为 11 等价于 yjy_j 的第 bb 位等于 xix_i 第 bb 位的取反。记

wanti=(xi 的第 b 位)⊕1,\mathrm{want}_i = \text{(}x_i \text{ 的第 } b \text{ 位)} \oplus 1,

于是整个子矩形的按位计数是

cnt1=∑i=ud#{ j∈[l,r]  ∣  yj 的第 b 位=wanti }.\mathrm{cnt}_1 = \sum_{i=u}^{d} \#\{\, j \in [l,r] \;\big|\; y_j \text{ 的第 } b \text{ 位} = \mathrm{want}_i \,\}.

二维问题被拆成了 d−u+1d-u+1 个一维问题:在 YY 的区间 [l,r][l,r] 上,统计某一位等于某值的元素个数。 异或的每一位互不干扰,这是整个算法能拆开的根源。

关键观察三:可持久化 01-Trie 一次同时给出计数和下钻目标。 01-Trie 按位分层, 把一个数从高位到低位插入,每个节点记录子树元素个数,那么"第 bb 位等于 vv 的个数" 就是"沿第 bb 位对应的分支走到那个子树,读它的计数"。

要做区间 [l,r][l,r] 而不是整个 YY,经典手法是可持久化:roots[j] 表示只插入 y1..yjy_1..y_j 的那个版本。两个版本的节点逐位同步下钻时,

cnt(version r 的子树)−cnt(version l−1 的子树)\mathrm{cnt}\big(\text{version } r \text{ 的子树}\big) - \mathrm{cnt}\big(\text{version } l-1 \text{ 的子树}\big)

恰好是 Y[l..r]Y[l..r] 上落进这棵子树的元素个数——又因为 Trie 的层与位一一对应, “落进子树"就等于"前若干高位等于给定前缀”,正是逐位确定所需要的候选集合。

更妙的是下钻本身就是候选集合的收缩。对每个 ii 维护一对指针:

指针 含义
cur[i] 第 rr 版本中,代表"已确定前缀 + wanti\mathrm{want}_i"的那个节点
prv[i] 第 l−1l-1 版本中的同一位置

两者相减即当前候选集合(前缀已固定的那一批 AijA_{ij})的规模;若答案该位取 11, 就让所有 cur[i] / prv[i] 走 wanti\mathrm{want}_i 分支("也想取反过来那位"的那个方向), 取 00 则走另一位。n⩽1000n \leqslant 1000,把 d−u+1d-u+1 对指针整排一起推进只有 O(n)O(n) 的常数。

一次询问的执行流程:

  1. 把 cur[i] ← roots[r]、prv[i] ← roots[l-1](i=u..di = u..d);
  2. 从第 30 位往第 0 位,对每一位 bb:按上式累计 cnt1\mathrm{cnt}_1;
  3. k⩽cnt1k \leqslant \mathrm{cnt}_1 则答案该位记 1 并整排走 wanti\mathrm{want}_i 分支, 否则 k←k−cnt1k \leftarrow k - \mathrm{cnt}_1、该位记 0、整排走另一位;
  4. 31 位走完,累计出的二进制数就是第 kk 大。

下面用样例的第一次询问(X[u..d]=(1,2)X[u..d] = (1,2),Y[l..r]=(7,6)Y[l..r] = (7,6),k=2k = 2)逐位跟踪。 候选集合是 {6,7,5,4}\{6, 7, 5, 4\},其中 i=1i=1(x1=1x_1=1)贡献 {7,6}\{7, 6\}、i=2i=2(x2=2x_2=2)贡献 {5,4}\{5, 4\}; 表中"计数"一列是当前候选集合里该 ii 贡献的元素中、AA 的第 bb 位为 11 的个数:

位 bb x1,x2x_1, x_2 的该位 want1,want2\mathrm{want}_1, \mathrm{want}_2 i=1i=1 计数 i=2i=2 计数 cnt1\mathrm{cnt}_1 判断 答案位
30…3 0, 0 1, 1 0 0 0 2>02 > 0,kk 不变 0
2 0, 0 1, 1 2 2 4 2⩽42 \leqslant 4,取高 1
1 0, 1 1, 0 2 0 2 2⩽22 \leqslant 2,取高 1
0 1, 0 0, 1 1 0 1 2>12 > 1,k←1k \leftarrow 1 0

高位全 0 时 kk 不动。第 2 位上 i=1i=1 的 {7,6}\{7, 6\} 与 i=2i=2 的 {5,4}\{5, 4\} 都满足 yjy_j 的第 2 位 =wanti=1= \mathrm{want}_i = 1,四个数全在这一位为 1,cnt1=4\mathrm{cnt}_1 = 4; 取高之后两个 ii 的指针都沿"yjy_j 第 2 位为 1"的分支下钻,候选集合不变。 第 1 位时 x2x_2 的该位是 1,want2=0\mathrm{want}_2 = 0,而 {7,6}\{7, 6\} 的第 1 位全是 1, i=2i=2 的计数掉到 0;i=1i=1 那边仍是 2 个,共 cnt1=2\mathrm{cnt}_1 = 2,k=2k=2 刚好取高, 候选集合收缩为 {7,6}\{7, 6\}。第 0 位上 want1=0\mathrm{want}_1 = 0,{7,6}\{7, 6\} 里只有 66 的第 0 位为 0, 计数为 1,k=2>1k=2 > 1,只好取 0 并把 kk 减到 1,候选集合只剩 {6}\{6\}。 最终答案 1102=6110_2 = 6。✔

为什么不用别的结构? “区间内第 bb 位为 vv 的个数"也可以对每一位各开一个前缀和数组 (31 个长度为 mm 的数组),单次统计同样是 O(1)O(1)——但它没法回答"下钻到哪”, 每次收缩候选集合都得重新在 O(n)O(n) 个前缀和数组上对齐前缀,实现上等价于手写一棵 31 层 Trie。 可持久化 01-Trie 把"计数"和"下一步往哪走"放进同一个结构,代码反而更短; 它也正是这类"区间内按位第 kk 大"问题的标准工具。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 16:01
# update_at: 2026-10-07 16:01

import sys

BITS = 31  # X_i, Y_j < 2^31,二进制位编号 0..30,求第 k 大时从最高位 30 开始贪心

# 可持久化 01-Trie 的节点池:三个平行列表按编号存节点,编号 0 是全局空节点
L: list[int] = [0]    # 第 0 分支(这一位为 0)的儿子编号
R: list[int] = [0]    # 第 1 分支的儿子编号
CNT: list[int] = [0]  # 子树里的元素个数


def child(idx: int, bit: int) -> int:
    """取节点 idx 的第 bit 个儿子编号(bit 为 0 走 L,为 1 走 R)。"""
    return R[idx] if bit else L[idx]


def build(y: list[int]) -> list[int]:
    """逐元素插入 y,返回 roots[j] = 只含 y[0..j-1] 的 Trie 根编号。"""
    roots = [0]
    for value in y:
        par = roots[-1]           # 上一个版本的根,也是本条链的复制来源
        root = len(CNT)           # 复制旧根开新点,新版本计数加一
        L.append(L[par])
        R.append(R[par])
        CNT.append(CNT[par] + 1)
        cur = root
        for b in range(BITS - 1, -1, -1):
            bit = value >> b & 1
            par = child(par, bit)
            nxt = len(CNT)        # 复制要下钻的旧子树
            L.append(L[par])
            R.append(R[par])
            CNT.append(CNT[par] + 1)
            if bit:
                R[cur] = nxt      # 只改下钻的那一支,另一支继续共享旧版本
            else:
                L[cur] = nxt
            cur = nxt
        roots.append(root)
    return roots


def kth(xs: list[int], roots: list[int], l: int, r: int, k: int) -> int:
    """在 i∈[u,d]、j∈[l,r] 的 A[i][j]=X[i]^Y[j] 中求第 k 大,xs 就是 X[u..d]。"""
    cur = [roots[r]] * len(xs)      # 版本 r 上每个 X[i] 各自的下钻指针
    prv = [roots[l - 1]] * len(xs)  # 版本 l-1 上的对应指针:两者相减得到区间 [l,r] 的计数
    ans = 0
    for b in range(BITS - 1, -1, -1):
        # A 的第 b 位为 1 ⟺ Y 的第 b 位等于 X 的第 b 位取反,先数出这一半的个数
        wants = [(x >> b & 1) ^ 1 for x in xs]
        cnt1 = sum(
            CNT[child(c, w)] - CNT[child(p, w)] for w, c, p in zip(wants, cur, prv)
        )
        take_high = k <= cnt1  # 第 k 大落在"当前位为 1"的那一半里
        if not take_high:
            k -= cnt1          # 跳过整半个高位区间,去低半区里找第 k 大
        ans |= take_high << b
        # 整排指针一起下钻:取高走 want 分支,取低走 want 的取反(正是 X 的这一位)
        step = [w ^ 1 if not take_high else w for w in wants]
        cur = [child(c, s) for c, s in zip(cur, step)]
        prv = [child(p, s) for p, s in zip(prv, step)]
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    X = [next(data) for _ in range(n)]
    Y = [next(data) for _ in range(m)]

    roots = build(Y)

    p = next(data)
    out: list[str] = []
    for _ in range(p):
        u, d, l, r, k = next(data), next(data), next(data), next(data), next(data)
        # X 的下标从 1 开始,X[u-1:d] 就是题面的 X[u..d]
        out.append(str(kth(X[u - 1:d], roots, l, r, k)))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 16:01
 * update_at: 2026-10-07 16:01
 */

// 一本通 1702《异或运算》正式解
//
// 题意:X[1..n]、Y[1..m],矩阵 A[i][j] = X[i] xor Y[j]。
// 每次询问矩形 i∈[u,d]、j∈[l,r] 中第 k 大的 A[i][j]。
//
// 关键观察:
//   1. 第 k 大从高位往低位定答案,只需要"候选集合里当前位为 1 的元素有多少个"。
//   2. 对固定的位 b 和固定的 X[i],A[i][j] 的第 b 位为 1 等价于 Y[j] 的第 b 位
//      等于 (X[i]>>b)&1 的取反;所以统计 Y 的区间 [l,r] 上"某一位等于某值"的个数,
//      就把二维问题拆成了一维的区间按位计数。
//   3. 可持久化 01-Trie 的前缀版本 roots[j] 恰好提供"区间 [l,r] 上某一位为某值"的计数:
//      cnt(roots[r] 的第 want 棵子树) - cnt(roots[l-1] 的第 want 棵子树)。
//   4. n 只有 1000,每次询问可以把 d-u+1 个 X[i] 对应的 Trie 指针整排一起往下走,
//      逐位累计 cnt1 决定答案这一位是 1 还是 0。
//
// 复杂度:建树 O(31m),单次询问 O(31(d-u+1)),总 O(31(m + pn)),n≤1000、m≤300000、p≤500 可行。

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

typedef long long ll;

const int MAXB = 31;             // X_i, Y_j < 2^31,二进制位编号 0..30
const int MAXM = 300005;         // Y 的长度上界
const int MAXN = 1005;           // X 的长度上界
const int MAXNODE = (MAXM + 5) * 32; // 可持久化 Trie 节点数:每个元素一条链,链长 32

struct Node {
    int ch[2]; // 两个儿子(对应二进制位 0/1)的编号,0 表示空
    int cnt;   // 该子树里元素的个数
};

Node node[MAXNODE]; // 动态化静态:所有 Trie 节点放在一个静态数组里,用 node_cnt 开点
int node_cnt;       // 已经开出的节点个数,节点 0 是全局空节点

ll X[MAXN];         // 数列 X,下标从 1 开始
int roots[MAXM];    // roots[j] = 只插入 Y[1..j] 的 Trie 的根编号

// 复制节点 from 开出一个新点,返回新点编号(可持久化的"版本复制")
int new_node(int from) {
    node_cnt++;
    node[node_cnt] = node[from];
    return node_cnt;
}

// 在版本 prev 的基础上插入 val,返回新版本的根编号
int insert(int prev, ll val) {
    int root = new_node(prev);
    int cur = root;
    node[cur].cnt++;
    for (int b = MAXB - 1; b >= 0; b--) {
        int bit = (val >> b) & 1; // 当前位的取值
        int nxt = new_node(node[prev].ch[bit]); // 复制要下钻的那棵子树
        node[cur].ch[bit] = nxt;
        cur = nxt;
        prev = node[prev].ch[bit];
        node[cur].cnt++; // 新版本里这条链上的计数都加一
    }
    return root;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        scanf("%lld", &X[i]);
    }

    node_cnt = 0;
    for (int j = 1; j <= m; j++) {
        ll v;
        scanf("%lld", &v);
        roots[j] = insert(roots[j - 1], v);
    }

    int p;
    scanf("%d", &p);
    while (p--) {
        int u, d, l, r, k;
        scanf("%d %d %d %d %d", &u, &d, &l, &r, &k);

        // 每行 X[i] 各自带一对 Trie 指针:cur[i] 是版本 r 的当前节点,
        // prv[i] 是版本 l-1 的当前节点,二者相减就是 Y[l..r] 上这段的计数。
        int cur[MAXN], prv[MAXN];
        for (int i = u; i <= d; i++) {
            cur[i] = roots[r];
            prv[i] = roots[l - 1];
        }

        ll ans = 0;
        for (int b = MAXB - 1; b >= 0; b--) {
            int cnt1 = 0; // 候选集合里 A 的第 b 位为 1 的元素个数
            for (int i = u; i <= d; i++) {
                int xb = (X[i] >> b) & 1;
                int want = xb ^ 1; // 想让 A 的第 b 位为 1,Y 的第 b 位必须是 xb 取反
                cnt1 += node[node[cur[i]].ch[want]].cnt - node[node[prv[i]].ch[want]].cnt;
            }

            int bit; // 答案当前位的取值
            if (k <= cnt1) {
                // 第 k 大落在"当前位为 1"的那一半里,答案这一位取 1,指针走 want 分支
                bit = 1;
                for (int i = u; i <= d; i++) {
                    int want = ((X[i] >> b) & 1) ^ 1;
                    cur[i] = node[cur[i]].ch[want];
                    prv[i] = node[prv[i]].ch[want];
                }
            } else {
                // 当前位为 1 的元素全被跳过,把 k 减去它们,指针走另一位
                k -= cnt1;
                bit = 0;
                for (int i = u; i <= d; i++) {
                    int want = (X[i] >> b) & 1;
                    cur[i] = node[cur[i]].ch[want];
                    prv[i] = node[prv[i]].ch[want];
                }
            }
            ans |= (ll)bit << b;
        }

        printf("%lld\n", ans);
    }

    return 0;
}

复杂度

  • 时间:建树每插入一个 YY 元素要走 31 层并复制 31 个节点,共 O(31m)O(31m)。 单次询问对 d−u+1d-u+1 个 ii 走 31 层,每层 O(1)O(1),共 O(31(d−u+1))O(31(d-u+1)), 总时间 O(31(m+pn))O\big(31(m + pn)\big)。取上限 m=3×105m = 3 \times 10^5、p=500p = 500、n=1000n = 1000: 约 9.3×106+1.55×107≈2.5×1079.3 \times 10^6 + 1.55 \times 10^7 \approx 2.5 \times 10^7 次基本操作。
  • 空间:可持久化 Trie 每个元素占 31+131 + 1 个节点,节点存两个儿子编号和一个计数, 共 O(31m)O(31m) 个节点、约 113113 MB。C++ 用静态 Node 数组(int ch[2]; int cnt; 一个节点 12 字节) 实测峰值 113.2113.2 MB;Python 用三个 list[int]。
  • 与 C++ 解法的关系:main.cpp 是同一算法的 C++ 落地,节点做成 struct Node { int ch[2]; int cnt; } 的动态化静态数组,用 node_cnt 当期分配指针; Python 版把 ch[2] 摊成 L / R 两个列表以省掉下标算术,两者逐位逻辑一致。
  • 实测(本机 /opt/homebrew/bin/g++-16 -O2 与 CPython 3.13,数据 m=3×105m = 3 \times 10^5、p=500p = 500、n=1000n = 1000 的顶格点): C++ 约 0.150.15 s / 峰值 113113 MB(限时 2 s、限内存 512 MB); Python 约 3.5∼3.93.5 \sim 3.9 s,在 2 s 限时下有 TLE 风险,仅作教学对照。

总结

  • 第 kk 大不必排序:二进制下的"字典序第 kk 大"可以逐位确定, 每层只需回答"当前位为 1 的元素有多少个",把 O(Nlog⁡N)O(N \log N) 的排序换成 log⁡V\log V 次计数。
  • 异或让二维可拆:AijA_{ij} 的第 bb 位只由 xi,yjx_i, y_j 的第 bb 位决定, 于是"矩形内的按位计数"→\to ∑i\sum_i"Y[l..r]Y[l..r] 上第 bb 位等于 wanti\mathrm{want}_i 的个数"。
  • 可持久化版本差 = 区间计数:cnt(roots[r]) - cnt(roots[l-1]) 是"区间 [l,r][l,r] 落进该子树" 的标准写法,把区间查询转成两个前缀版本的同步下钻。
  • 下钻即收缩候选集合:逐位贪心的每一步同时完成两件事——统计 cnt1\mathrm{cnt}_1、 把指针移到答案该位对应的分支。这是"可持久化 Trie 求区间异或第 kk 大"的通用套路, 本题只是把单个 YY 换成了 nn 排指针并行推进。
  • 注意值域:xi,yj<231x_i, y_j < 2^{31} 所以只有 0…30 共 31 位,答案同样落在 [0,231)[0, 2^{31}), C++ 里用 long long 承接即可,不需要 unsigned。