连续数字区间

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

把区间连续化为 l + cnt(l,r) == r,扫右端点用线段树维护 mx[l] 的前缀最大值,询问按右端点分桶后按 x 递减结算,得到最短连续区间。

OJ: roj

题目 ID: 1733

难度:提高+/省选-

标签:线段树堆贪心扫描线python

创建: 2026-10-07 19:20

更新: 2026-10-07 19:20

形式化题目

给定 1∼n1 \sim n 的一个排列 a1,a2,…,ana_1, a_2, \dots, a_n。称区间 [l,r][l, r] 是连续的,若 {al,…,ar}\{a_l, \dots, a_r\} 排序后是一列连续整数;等价的写法是

max⁡(al,…,ar)−min⁡(al,…,ar)=r−l.\max(a_l, \dots, a_r) - \min(a_l, \dots, a_r) = r - l .

给出 mm 个询问,每个询问是位置区间 [xi,yi][x_i, y_i](1⩽xi⩽yi⩽n1 \leqslant x_i \leqslant y_i \leqslant n), 要求找出一个连续的区间 [li,ri]⊇[xi,yi][l_i, r_i] \supseteq [x_i, y_i],使长度 ri−lir_i - l_i 最小; 输出这个 li,ril_i, r_i。

1⩽n,m⩽1051 \leqslant n, m \leqslant 10^5。注意题目问的是位置上的包含关系: [li,ri][l_i, r_i] 要覆盖位置 xix_i 到 yiy_i,而不是覆盖某段值域。

正解

思路

为什么不能只盯住值域。 朴素想法是把 axi,…,ayia_{x_i}, \dots, a_{y_i} 的值扩张到连续区间, 再把落在外面的值一个个拉进来。但题面约束是位置:[xi,yi][x_i, y_i] 里的位置必须整段留在 [li,ri][l_i, r_i] 内,而位置是散开的,值连续和位置连续之间没有简单对应。所以必须换一个 能同时看到"位置"和"值的相邻关系"的刻画。

关键刻画一:用相邻值对计数。

记 cnt(l,r)cnt(l, r) 为满足"vv 与 v+1v+1 都落在 [l,r][l, r] 内"的值 vv 的个数 (值 vv 在 [l,r][l,r] 内指 ∃i∈[l,r],ai=v\exists i \in [l,r], a_i = v)。因为 aa 是排列,[l,r][l, r] 内的 r−l+1r - l + 1 个值互不相同,把它们排序成 v1<v2<⋯<vkv_1 < v_2 < \dots < v_k(k=r−l+1k = r - l + 1), 则 cnt(l,r)cnt(l, r) 恰好等于满足 vj+1=vj+1v_{j+1} = v_j + 1 的 jj 的个数。于是

cnt(l,r)=r−l  ⟺  相邻两数之差全为 1  ⟺  [l,r] 连续,cnt(l, r) = r - l \iff \text{相邻两数之差全为 } 1 \iff [l, r] \text{ 连续},

而 cnt(l,r)⩽r−lcnt(l, r) \leqslant r - l 恒成立(只有 k−1k-1 个数对)。这个刻画的好处是 cntcnt 只关心"某两个值的位置是否都落进区间",也就是只关心位置,恰好对上了题面的约束。

关键刻画二:把 cntcnt 的增量摊到左端点上。

固定右端点 ii,对每个左端点 l⩽il \leqslant i 定义

mx[l]=l+cnt(l,i).mx[l] = l + cnt(l, i).

由上面的等价性,[l,i][l, i] 连续   ⟺  mx[l]=i\iff mx[l] = i;又因 cnt(l,i)⩽i−lcnt(l, i) \leqslant i - l, 总有 mx[l]⩽imx[l] \leqslant i。所以扫到 ii 时,mx[l]=imx[l] = i 就是"[l,i][l,i] 连续"的判据。

ii 增加时 mxmx 怎么变?设 w=aiw = a_i,考虑值对 (w−1,w)(w-1, w) 与 (w,w+1)(w, w+1)。 对其中一个值对,若另一个值 uu 的位置 pp 满足 p<ip < i,那么从这一刻起, 所有 l⩽pl \leqslant p 的区间 [l,i][l, i] 都同时含有 uu 与 ww,即这个值对对它们成立; 而 l>pl > p 的区间不含 uu,不成立。于是 cntcnt 的变化是一次前缀加:

mx[l]+=1(1⩽l⩽p).mx[l] \mathrel{+}= 1 \quad (1 \leqslant l \leqslant p).

两个值对各贡献一次前缀加(uu 还不存在,即 p=0p = 0 时无贡献)。这样每次 ii 的推进 只要 O(log⁡n)O(\log n)。

前缀加 + 前缀最大:换成差分数组 + 线段树。

前缀加如果直接在线段树上做区间加也行,但本题还要取"前缀里 mxmx 最大者的最大 ll", 把前缀加写成差分更好写:维护差分数组 dd(d[l]=mx[l]−mx[l−1]d[l] = mx[l] - mx[l-1],mx[0]=0mx[0] = 0), 则 mx[l]=∑j⩽ld[j]mx[l] = \sum_{j \leqslant l} d[j],前缀加 [1,p][1, p] 退化成两个单点加 (d[1]+=1d[1] \mathrel{+}= 1、d[p+1]−=1d[p+1] \mathrel{-}= 1)。线段树上每个节点存 (本段 d 之和, 本段内自段左端起算的最大前缀和, 取到它的最大下标)(\text{本段 } d \text{ 之和},\ \text{本段内自段左端起算的最大前缀和},\ \text{取到它的最大下标}), 合并时左段的最大前缀和与"左段和 + 右段最大前缀和"取较大者、平手取更靠右的下标, 就能在 O(log⁡n)O(\log n) 内得到 max⁡l⩽xmx[l]\max_{l \leqslant x} mx[l] 以及取到它的最大 ll。

用题目样例 a=(3,1,7,5,6,4,2)a = (3,1,7,5,6,4,2) 走一遍前几步,看 mx[l]=l+cnt(l,i)mx[l] = l + cnt(l, i) 是怎么长起来的 (表中横轴是 ll,纵轴是扫到的右端点 ii;每行只列该 ii 下的 l=1∼7l = 1 \sim 7):

ii aia_i 触发的值对(另一端位置) 1 2 3 4 5 6 7
0 — — 1 2 3 4 5 6 7
1 3 (3,4)(3,4):4 在位置 6,未出现 1 2 3 4 5 6 7
2 1 (1,2)(1,2):2 在位置 7,未出现 1 2 3 4 5 6 7
3 7 (6,7)(6,7):6 在位置 5,未出现 1 2 3 4 5 6 7
4 5 (4,5)(4,5):4 在位置 6,未出现 1 2 3 4 5 6 7
5 6 (5,6)(5,6):5 在位置 4 → 前缀 [1,4][1,4] 加一;(6,7)(6,7):7 在位置 3 → 前缀 [1,3][1,3] 加一 3 4 5 5 5 6 7
6 4 (3,4)(3,4):3 在位置 1 → 前缀 [1,1][1,1] 加一;(4,5)(4,5):5 在位置 4 → 前缀 [1,4][1,4] 加一 5 5 6 6 5 6 7
7 2 (1,2)(1,2):1 在位置 2 → 前缀 [1,2][1,2] 加一;(2,3)(2,3):3 在位置 1 → 前缀 [1,1][1,1] 加一 7 6 6 6 5 6 7

看 i=6i = 6 这一行:mx[3]=6=imx[3] = 6 = i,说明 [3,6][3, 6] 连续,正是询问 3 6 的答案左端点 l=3l = 3; 同一行里 mx[1]=5≠6mx[1] = 5 \neq 6,说明询问 1 3 在 i=6i = 6 时还结算不了。 到 i=7i = 7 这一行,mx[7]=7mx[7] = 7 给出询问 7 7 的 l=7l = 7(平手取最大 ll,mx[7]mx[7] 与 mx[1]mx[1] 并列最大,但 77 更靠右),mx[1]=7mx[1] = 7 又给出询问 1 3 的 l=1l = 1,与样例一致。 另外注意每行都有 mx[l]⩽imx[l] \leqslant i,这正是把 mx[l]=imx[l] = i 当作判据的依据。

询问怎么结算。

询问按右端点分桶:by_y[y] 存所有 yi=yy_i = y 的询问。扫到 ii 时把 by_y[i] 的询问 全部压进一个按 xx 递减的大根堆,然后反复看堆顶 (x,id)(x, id):

  • 若 max⁡l⩽xmx[l]=i\max_{l \leqslant x} mx[l] = i,则 [l∗,i][l^*, i] 是包含 [x,i][x, i] 的连续区间,其中 l∗l^* 是取到该最大值的最大 ll;记下答案并弹堆;
  • 否则退出循环,把这个询问留给更大的 ii。

这个"否则就整体退出"之所以安全,是因为 [1,x′]⊆[1,x][1, x'] \subseteq [1, x] 时 max⁡l⩽x′mx[l]⩽max⁡l⩽xmx[l]\max_{l \leqslant x'} mx[l] \leqslant \max_{l \leqslant x} mx[l]:堆顶(xx 最大)都做不到, xx 更小的更做不到。于是每一轮 ii 恰好结算掉所有"该在 ii 结算"的询问, 每个询问只弹一次堆。

为什么"最早能结算的 ii"就是最优的右端点。

先说明答案唯一。若 [l1,r1][l_1, r_1] 与 [l2,r2][l_2, r_2] 都是包含 [x,y][x, y] 的连续区间,设它们的值集合 分别是 [A1,B1][A_1, B_1]、[A2,B2][A_2, B_2],则交集位置区间 [L,R]=[max⁡(l1,l2),min⁡(r1,r2)][L, R] = [\max(l_1, l_2), \min(r_1, r_2)] 满足 a[L..R]=[max⁡(A1,A2),min⁡(B1,B2)]a[L..R] = [\max(A_1, A_2), \min(B_1, B_2)](落在交集位置上的值必在两个值集合里; 反之两个值集合公共的值在两个原区间里的位置都落在交集内),即交集也是连续区间, 且仍包含 [x,y][x, y]。所以长度最短的连续区间唯一,算法不存在"两个都最短"的歧义。

再说明算法拿到的就是它。设答案区间为 [L,R][L, R],则 RR 是"存在 l⩽xl \leqslant x 使 [l,r][l, r] 连续"的最小 r⩾yr \geqslant y,这恰好是询问第一次变得可结算的 ii(堆保证了它从 yy 起 每轮都被检查到,一旦可结算立刻结算)。而在 i=Ri = R 这一轮,凡是满足 l⩽xl \leqslant x 且 [l,R][l, R] 连续的 ll,都给出一个包含 [x,y][x, y] 的连续区间,其中长度最短的正是最大的 ll, 也就是线段树返回的那个 l∗l^*;由答案的唯一性 l∗=Ll^* = L。所以算法输出 [L,R][L, R],正确。

代码

Python 版(main.py,线段树用显式数组 + 迭代式前缀查询):

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 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,同一算法,线段树写成递归函数):

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;
}

复杂度

  • 时间:扫 i=1∼ni = 1 \sim n,每个 ii 最多做两次单点加(O(log⁡n)O(\log n))、每个询问入堆一次、 出堆一次(O(log⁡m)O(\log m)),加上每次出堆前一次前缀查询 O(log⁡n)O(\log n)。 总计 O((n+m)log⁡n)O((n + m) \log n),顶格 n=m=105n = m = 10^5 时约 3.4×1063.4 \times 10^6 次基本操作, C++ 实测远低于 1000 ms 的限制。
  • 空间:线段树 4n4n 个节点、by_y 分桶 O(n+m)O(n + m)、堆 O(m)O(m),合计 O(n+m)O(n + m); C++ 约 10 MB,Python 因为存了元组与列表会到几十 MB,都在 512 MB 之内。
  • 与 C++ 解法的关系:两版是同一算法,区别只在实现细节——C++ 递归线段树 把"左段和 + 右段最大前缀和"写在 merge_node() 里,Python 用显式数组做迭代式前缀查询, 并把 size 补到 2 的幂以便逐层下降;补出来的空叶子把"本段最大前缀和"置为哨兵 NEG,保证它永远不会被选成答案。Python 版额外在"所有询问都已结算"时提前跳出 右端点扫描(此时再往右扫只会得到更长的区间),这是个与正确性无关的常数优化, 顶格数据下 Python 约 1 秒,算法与 C++ 同阶,不存在为了跑得快而降级成暴力的地方。

总结

  • 把"连续"翻译成计数等式:[l,r][l, r] 连续   ⟺  cnt(l,r)=r−l\iff cnt(l, r) = r - l, 其中 cntcnt 数的是"相邻值对同时落进区间"的个数。这一步把值域上的连续性换成了 位置上的落点问题,才有可能对位置区间做数据结构。
  • 前缀加变成差分单点加:mx[l]=l+cnt(l,i)mx[l] = l + cnt(l, i) 的更新是前缀加, 写成差分后线段树只需支持单点加 + 前缀最大(含"取最大下标")。
  • 单调性决定结算顺序:max⁡l⩽xmx[l]\max_{l \leqslant x} mx[l] 对 xx 单调不减, 所以询问按 xx 递减检查、遇到做不到的立刻停,能保证每个询问只在最优右端点处结算一次。
  • 答案唯一性来自交集封闭:两个包含 [x,y][x,y] 的连续区间的交集仍是连续区间且仍包含 [x,y][x,y],所以最短区间唯一,取"最大 ll"不是权宜之计而是唯一正确答案。
  • 与本题数据的关系:随仓数据由素材源的 data.py 生成(本题题面来自网络重建、 不是官方原始题面,出题意图与官方原题可能有偏差),其中点 9 是 ai=ia_i = i 的有序排列、 点 10 是 a=(n,1,2,…,n−1)a = (n, 1, 2, \dots, n-1) 且所有询问都是 x=1x = 1(mm 个询问全在 i=ni = n 结算, 专压堆与线段树的最坏负载)。这些结构点的答案有闭式,可用于交叉核对。