把区间连续化为 l + cnt(l,r) == r,扫右端点用线段树维护 mx[l] 的前缀最大值,询问按右端点分桶后按 x 递减结算,得到最短连续区间。
OJ: roj
题目 ID: 1733
难度:提高+/省选-
标签:线段树堆贪心扫描线python
创建: 2026-10-07 19:20
更新: 2026-10-07 19:20
形式化题目
给定
给出
正解
思路
为什么不能只盯住值域。 朴素想法是把
关键刻画一:用相邻值对计数。
记
而
关键刻画二:把
固定右端点
由上面的等价性,
两个值对各贡献一次前缀加(
前缀加 + 前缀最大:换成差分数组 + 线段树。
前缀加如果直接在线段树上做区间加也行,但本题还要取"前缀里
用题目样例
| 触发的值对(另一端位置) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
|---|---|---|---|---|---|---|---|---|---|
| 0 | — | — | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 3 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 2 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 3 | 7 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 4 | 5 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 5 | 6 | 3 | 4 | 5 | 5 | 5 | 6 | 7 | |
| 6 | 4 | 5 | 5 | 6 | 6 | 5 | 6 | 7 | |
| 7 | 2 | 7 | 6 | 6 | 6 | 5 | 6 | 7 |
看 3 6 的答案左端点 1 3 在 7 7 的 1 3 的
询问怎么结算。
询问按右端点分桶:by_y[y] 存所有 by_y[i] 的询问
全部压进一个按
- 若
,则 是包含 的连续区间,其中 是取到该最大值的最大 ;记下答案并弹堆; - 否则退出循环,把这个询问留给更大的
。
这个"否则就整体退出"之所以安全,是因为
为什么"最早能结算的
先说明答案唯一。若
再说明算法拿到的就是它。设答案区间为
代码
Python 版(main.py,线段树用显式数组 + 迭代式前缀查询):
#!/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 19:20
# update_at: 2026-10-07 19:20
import sys
from heapq import heappop, heappush
# 线段树节点:(本段差分数组之和, 本段内「自段左端起算的最大前缀和」, 取到它的最大下标)。
# 差分数组 d 的前缀和 d[0]+...+d[l] 就是 mx[l](1-based 的 mx[l+1])。
type Node = tuple[int, int, int]
type Query = tuple[int, int] # (询问左端点 x, 询问编号 id),1-based
type Tree = list[Node] # 迭代式线段树,tree[i] 就是节点 i(叶子在 [size, 2*size))
type Buckets = list[list[Query]] # by_y[y]:右端点为 y 的全部询问
NEG = -10**9 # 哨兵:补齐用的空叶子,其「最大前缀和」永不可能是答案
def merge(left: Node, right: Node) -> Node:
"""合并相邻两段,得到「最大前缀和 + 最大下标」;平手取更靠右的下标。"""
total = left[0] + right[0]
cross = left[0] + right[1] # 跨过分界的候选:左段整段和 + 右段的最大前缀和
if cross >= left[1]: # 平手取 right[2](更靠右的下标)
return (total, cross, right[2])
return (total, left[1], left[2])
def point_add(tree: Tree, size: int, pos: int, delta: int) -> None:
"""给差分数组的第 pos 位(0-based)加上 delta,并沿路重算祖先。"""
i = size + pos
total, best, arg = tree[i]
tree[i] = (total + delta, best + delta, arg)
i >>= 1
while i:
tree[i] = merge(tree[2 * i], tree[2 * i + 1])
i >>= 1
def add_prefix(tree: Tree, size: int, n: int, p: int) -> None:
"""把 mx[1..p] 整体加一:差分数组上只有第 0 位 +1、第 p 位 -1(p 是 0-based 的 p)。"""
point_add(tree, size, 0, 1)
if p < n:
point_add(tree, size, p, -1)
def prefix_max(tree: Tree, size: int, count: int) -> Node:
"""求 mx[1..count] 的最大值(存在 best 位)及取到它的最大左端点(0-based 存在 arg 位)。"""
node, lo, hi = 1, 0, size
acc: Node | None = None
while True:
if count == hi - lo: # 整段都被覆盖,直接取这一段
return tree[node] if acc is None else merge(acc, tree[node])
mid = (lo + hi) >> 1
if count <= mid - lo: # 只在左孩子里找
node, hi = 2 * node, mid
else: # 左孩子整段收下,再进右孩子找剩余部分
acc = tree[2 * node] if acc is None else merge(acc, tree[2 * node])
count -= mid - lo
node, lo = 2 * node + 1, mid
def answer_all(n: int, a: list[int], pos_of_val: list[int],
by_y: Buckets, m: int) -> tuple[list[int], list[int]]:
"""扫右端点 i,用线段树维护 mx[l] = l + cnt(l, i),在每个询问的闭包右端点处结算答案。"""
size = 1
while size < n:
size <<= 1
# 叶子 i 表示差分数组 d[i](0-based),它的前缀和就是 mx[i+1]。初值 d[i] = 1。
# 下标 [n, size) 是补齐出来的空叶子:和不贡献(sum = 0)、最大前缀和取哨兵。
tree: Tree = [(0, NEG, i) for i in range(2 * size)]
for i in range(n):
tree[size + i] = (1, 1, i)
for i in range(size - 1, 0, -1):
tree[i] = merge(tree[2 * i], tree[2 * i + 1])
ans_l = [0] * m
ans_r = [0] * m
heap: list[tuple[int, int]] = [] # 存 (-x, id),堆顶就是 x 最大的未结算询问
answered = 0 # 已结算的询问数,全部结算完就不必再往后扫
for right in range(1, n + 1):
w = a[right]
# 值对 (w-1, w) 与 (w, w+1):另一端已在 [1, right] 内出现时,从 right 起
# 它对每个 l <= 那个下标 的区间 [l, right] 都成立,于是前缀 [1, 那个下标] 加一。
for v in (w - 1, w + 1):
other = pos_of_val[v] # 未出现的值记 0,条件自然不成立
if 0 < other <= right:
add_prefix(tree, size, n, other)
for query in by_y[right]:
heappush(heap, (-query[0], query[1]))
while heap:
neg_x, id = heap[0]
_total, mx_best, mx_arg = prefix_max(tree, size, -neg_x)
if mx_best != right: # 堆顶(x 最大)都做不到,其余更做不到
break
heappop(heap)
ans_l[id], ans_r[id] = mx_arg + 1, right
answered += 1
if answered == m: # 所有询问都有答案了,后面的右端点只可能更长
break
return ans_l, ans_r
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
a = [0] * (n + 1)
pos_of_val = [0] * (n + 2) # 值 v 所在下标,0 表示还没出现
for i in range(1, n + 1):
a[i] = next(data)
pos_of_val[a[i]] = i
m = next(data)
by_y: Buckets = [[] for _ in range(n + 1)]
for id in range(m):
x, y = next(data), next(data)
by_y[y].append((x, id))
ans_l, ans_r = answer_all(n, a, pos_of_val, by_y, m)
out = [f"{ans_l[i]} {ans_r[i]}" for i in range(m)]
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()C++ 版(main.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 19:20
* update_at: 2026-10-07 19:20
*/
// 连续数字区间:扫右端点 + 线段树维护「左端点的相邻值对数」
//
// 记 cnt(l, r) 为满足「值 v 与 v+1 都落在 [l, r] 内」的 v 的个数。排列内部的值互不相同,
// 把它排序后相邻两数之差全为 1 ⟺ 这样的 v 恰有 r - l 个,故
// [l, r] 连续 ⟺ l + cnt(l, r) == r。
// 于是扫右端点 i = 1..n,只维护关于左端点 l 的 mx[l] = l + cnt(l, i):加入 a[i] = w 时,
// 值对 (w-1, w)、(w, w+1) 中「两端下标都不超过 i」的那些,会让所有 l <= 较小下标 的
// mx[l] 加一(一次前缀加)。mx[l] <= i 恒成立,且 mx[l] == i ⟺ [l, i] 连续。
// 询问按右端点 y 分桶,扫到 i 时把 y == i 的询问按 x 从大到小检查:x 最大的都做不到,
// 其余 x 更小的更做不到。前缀加 + 前缀最大用差分数组换成单点加 + 最大前缀和。
//
// 复杂度:O((n + m) log n) 时间、O(n + m) 空间。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
const ll NEG = -1000000000; // 空节点的哨兵:绝不可能被选为最大前缀和
ll n, m;
ll a[MAXN]; // 输入排列,下标 1..n
ll pos_of_val[MAXN]; // pos_of_val[v]:值 v 在排列中的下标
// 线段树节点:维护差分数组 d 的一段,d 的前缀和就是 mx[l]
struct SegNode {
ll sum; // 这一段 d 的和
ll best; // 这一段内「从本段左端起算的前缀和」的最大值,即这一段里 mx 的最大值
ll arg; // 取到 best 的最大的 l(1-based)
};
SegNode seg[MAXN * 4];
struct Ask {
ll x; // 询问左端点
ll id; // 询问编号
};
struct Answer {
ll l; // 最短连续区间的左端点
ll r; // 最短连续区间的右端点
};
vector<Ask> by_y[MAXN]; // by_y[y]:右端点为 y 的全部询问
priority_queue<pair<ll, ll> > heap_ask; // (x, id) 大根堆,按 x 从大到小结算
Answer ans[MAXN]; // 每个询问的答案
// 按从左到右的顺序把两段合并成一段;前缀和最大值平手时取更大的 l(即右段的答案)。
SegNode merge_node(const SegNode &left_part, const SegNode &right_part) {
SegNode res;
res.sum = left_part.sum + right_part.sum;
if (left_part.sum + right_part.best >= left_part.best) {
res.best = left_part.sum + right_part.best;
res.arg = right_part.arg;
} else {
res.best = left_part.best;
res.arg = left_part.arg;
}
return res;
}
// 由两个孩子重算节点 now。
void pull_up(ll now) {
seg[now] = merge_node(seg[now << 1], seg[now << 1 | 1]);
}
// 建树:d 的初值全为 1,此时 mx[l] = l。
void build(ll now, ll l, ll r) {
if (l == r) {
seg[now].sum = 1;
seg[now].best = 1;
seg[now].arg = l;
return;
}
ll mid = (l + r) >> 1;
build(now << 1, l, mid);
build(now << 1 | 1, mid + 1, r);
pull_up(now);
}
// 给 d[pos] 加上 c(单点加),并自底向上重算沿途节点。
void point_add(ll now, ll l, ll r, ll pos, ll c) {
if (l == r) {
seg[now].sum += c;
seg[now].best += c;
return;
}
ll mid = (l + r) >> 1;
if (pos <= mid) point_add(now << 1, l, mid, pos, c);
else point_add(now << 1 | 1, mid + 1, r, pos, c);
pull_up(now);
}
// 询问 l ∈ [1, x] 内 mx[l] 的最大值以及取到它的最大 l。
SegNode query_prefix(ll now, ll l, ll r, ll x) {
if (r <= x) return seg[now];
ll mid = (l + r) >> 1;
if (x <= mid) return query_prefix(now << 1, l, mid, x);
return merge_node(seg[now << 1], query_prefix(now << 1 | 1, mid + 1, r, x));
}
// 把 mx[1..p] 全部加一:差分数组 d 上只需 d[1] += 1、d[p+1] -= 1。
void add_prefix(ll p) {
point_add(1, 1, n, 1, 1);
if (p < n) point_add(1, 1, n, p + 1, -1);
}
void read_input() {
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
pos_of_val[a[i]] = i;
}
cin >> m;
for (ll i = 1; i <= m; i++) {
Ask ask;
ll y;
cin >> ask.x >> y;
ask.id = i;
by_y[y].push_back(ask);
}
}
void solve() {
build(1, 1, n);
for (ll i = 1; i <= n; i++) {
ll w = a[i];
// 值对 (w-1, w) 与 (w, w+1):另一端的下标不超过 i 时,从 i 起对每个
// l <= 那个下标 的区间 [l, i] 都成立,于是给前缀 [1, 那个下标] 加一。
if (w - 1 >= 1 && pos_of_val[w - 1] <= i) add_prefix(pos_of_val[w - 1]);
if (w + 1 <= n && pos_of_val[w + 1] <= i) add_prefix(pos_of_val[w + 1]);
for (size_t j = 0; j < by_y[i].size(); j++) {
heap_ask.push(make_pair(by_y[i][j].x, by_y[i][j].id));
}
// 堆顶是 x 最大的询问;它都做不到时,x 更小的询问更做不到。
while (!heap_ask.empty()) {
pair<ll, ll> top = heap_ask.top();
SegNode res = query_prefix(1, 1, n, top.first);
if (res.best != i) break;
ans[top.second].l = res.arg;
ans[top.second].r = i;
heap_ask.pop();
}
}
for (ll i = 1; i <= m; i++) cout << ans[i].l << ' ' << ans[i].r << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
- 时间:扫
,每个 最多做两次单点加( )、每个询问入堆一次、 出堆一次( ),加上每次出堆前一次前缀查询 。 总计 ,顶格 时约 次基本操作, C++ 实测远低于 1000 ms 的限制。 - 空间:线段树
个节点、 by_y分桶、堆 ,合计 ; C++ 约 10 MB,Python 因为存了元组与列表会到几十 MB,都在 512 MB 之内。 - 与 C++ 解法的关系:两版是同一算法,区别只在实现细节——C++ 递归线段树
把"左段和 + 右段最大前缀和"写在
merge_node()里,Python 用显式数组做迭代式前缀查询, 并把size补到 2 的幂以便逐层下降;补出来的空叶子把"本段最大前缀和"置为哨兵NEG,保证它永远不会被选成答案。Python 版额外在"所有询问都已结算"时提前跳出 右端点扫描(此时再往右扫只会得到更长的区间),这是个与正确性无关的常数优化, 顶格数据下 Python 约 1 秒,算法与 C++ 同阶,不存在为了跑得快而降级成暴力的地方。
总结
- 把"连续"翻译成计数等式:
连续 , 其中 数的是"相邻值对同时落进区间"的个数。这一步把值域上的连续性换成了 位置上的落点问题,才有可能对位置区间做数据结构。 - 前缀加变成差分单点加:
的更新是前缀加, 写成差分后线段树只需支持单点加 + 前缀最大(含"取最大下标")。 - 单调性决定结算顺序:
对 单调不减, 所以询问按 递减检查、遇到做不到的立刻停,能保证每个询问只在最优右端点处结算一次。 - 答案唯一性来自交集封闭:两个包含
的连续区间的交集仍是连续区间且仍包含 ,所以最短区间唯一,取"最大 "不是权宜之计而是唯一正确答案。 - 与本题数据的关系:随仓数据由素材源的
data.py生成(本题题面来自网络重建、 不是官方原始题面,出题意图与官方原题可能有偏差),其中点 9 是的有序排列、 点 10 是 且所有询问都是 ( 个询问全在 结算, 专压堆与线段树的最坏负载)。这些结构点的答案有闭式,可用于交叉核对。