把二维第 k 大按最高位贪心拆成逐位计数,用可持久化 01-Trie 上的前缀版本差得到区间按位个数,n 个 X 的指针整排一起下钻。
OJ: roj
题目 ID: 1702
难度:提高+/省选-
标签:可持久化Trie位运算二进制python
创建: 2026-10-07 16:01
更新: 2026-10-07 16:01
形式化题目
给定两个非负整数数列
构造
中第
数据规模:
以题目样例为例,
| 6 | 7 | 4 | |
| 5 | 4 | 7 | |
| 3 | 2 | 1 |
第一次询问取
正解
思路
先看朴素做法。 每次询问把子矩形里的
关键观察一:第
- 若最高位为
的元素有 个,且 , 则答案的最高位是 ,且第 大落在"最高位为 1"这一半里; - 否则答案最高位是
,并把 减去 ——那一半已经被整块跳过了。
确定一位后,候选集合收缩到对应的那一半,再对次高位做同样的事。 重复 31 次就得到完整答案。排序被换成了 31 次"某一半有多少个"的计数。
关键观察二:二维的位计数能拆成一维的按位计数。 对固定的
所以
于是整个子矩形的按位计数是
二维问题被拆成了
关键观察三:可持久化 01-Trie 一次同时给出计数和下钻目标。 01-Trie 按位分层,
把一个数从高位到低位插入,每个节点记录子树元素个数,那么"第
要做区间 roots[j] 表示只插入
恰好是
更妙的是下钻本身就是候选集合的收缩。对每个
| 指针 | 含义 |
|---|---|
cur[i] |
第 |
prv[i] |
第 |
两者相减即当前候选集合(前缀已固定的那一批 cur[i] / prv[i] 走
一次询问的执行流程:
- 把
cur[i] ← roots[r]、prv[i] ← roots[l-1](); - 从第 30 位往第 0 位,对每一位
:按上式累计 ; 则答案该位记 1 并整排走 分支, 否则 、该位记 0、整排走另一位; - 31 位走完,累计出的二进制数就是第
大。
下面用样例的第一次询问(
| 位 |
判断 | 答案位 | |||||
|---|---|---|---|---|---|---|---|
| 30…3 | 0, 0 | 1, 1 | 0 | 0 | 0 | 0 | |
| 2 | 0, 0 | 1, 1 | 2 | 2 | 4 | 1 | |
| 1 | 0, 1 | 1, 0 | 2 | 0 | 2 | 1 | |
| 0 | 1, 0 | 0, 1 | 1 | 0 | 1 | 0 |
高位全 0 时
为什么不用别的结构? “区间内第
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:建树每插入一个
元素要走 31 层并复制 31 个节点,共 。 单次询问对 个 走 31 层,每层 ,共 , 总时间 。取上限 、 、 : 约 次基本操作。 - 空间:可持久化 Trie 每个元素占
个节点,节点存两个儿子编号和一个计数, 共 个节点、约 MB。C++ 用静态 Node数组(int ch[2]; int cnt;一个节点 12 字节) 实测峰值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,数据、 、 的顶格点): C++ 约 s / 峰值 MB(限时 2 s、限内存 512 MB); Python 约 s,在 2 s 限时下有 TLE 风险,仅作教学对照。
总结
- 第
大不必排序:二进制下的"字典序第 大"可以逐位确定, 每层只需回答"当前位为 1 的元素有多少个",把 的排序换成 次计数。 - 异或让二维可拆:
的第 位只由 的第 位决定, 于是"矩形内的按位计数" " 上第 位等于 的个数"。 - 可持久化版本差 = 区间计数:
cnt(roots[r]) - cnt(roots[l-1])是"区间落进该子树" 的标准写法,把区间查询转成两个前缀版本的同步下钻。 - 下钻即收缩候选集合:逐位贪心的每一步同时完成两件事——统计
、 把指针移到答案该位对应的分支。这是"可持久化 Trie 求区间异或第 大"的通用套路, 本题只是把单个 换成了 排指针并行推进。 - 注意值域:
所以只有 0…30 共 31 位,答案同样落在 , C++ 里用 long long承接即可,不需要unsigned。