1 条题解

  • 0
    @ 2026-11-12 21:08:34

    T4 连续段(consecutive)题解

    题意简述

    给定一个 11 到 nn 的排列。称子数组 al,…,ara_l,\dots,a_r 为连续段,若 max⁡−min⁡=r−l\max-\min=r-l。对每个前缀 a1,…,aka_1,\dots,a_k,求其中连续段的数量。

    思路

    固定右端点

    固定右端点 rr,对每个左端点 l≤rl\le r 定义

    $$f_r(l)=\max_{l\le i\le r}a_i-\min_{l\le i\le r}a_i-(r-l).$$

    因为 aa 是排列,子数组中的 r−l+1r-l+1 个数互不相同,且都落在 [min⁡,max⁡][\min,\max] 内,所以

    $$\max-\min+1\ge r-l+1\quad\Longrightarrow\quad f_r(l)\ge 0.$$

    而 l=rl=r 时 max⁡=min⁡=ar\max=\min=a_r,故 fr(r)=0f_r(r)=0。于是

    [l,r] 是连续段  ⟺  fr(l)=0.[l,r]\text{ 是连续段}\iff f_r(l)=0.

    因此,若我们能对每个 rr 维护所有 fr(l)f_r(l),那么“以 rr 结尾的连续段数量”就是 [1,r][1,r] 中 fr(l)=0f_r(l)=0 的 ll 的个数。

    从 r−1r-1 到 rr

    加入 ara_r 时,ff 会发生三类变化:

    1. 长度项: −(r−l)-(r-l) 比 −(r−1−l)-(r-1-l) 少 11,所以所有 l∈[1,r−1]l\in[1,r-1] 的 ff 都减 11;
    2. 最大值项: 用单调递减栈维护最大值。当 ara_r 大于栈顶时,弹出栈顶 idxidx。设弹出后栈顶为 pp(空则为 00),则对于 l∈[p+1,idx]l\in[p+1,idx],最大值从 aidxa_{idx} 变成 ara_r,ff 增加 ar−aidxa_r-a_{idx};
    3. 最小值项: 用单调递增栈维护最小值。当 ara_r 小于栈顶时,弹出栈顶 idxidx。设弹出后栈顶为 pp,则对于 l∈[p+1,idx]l\in[p+1,idx],最小值从 aidxa_{idx} 变成 ara_r,ff 增加 aidx−ara_{idx}-a_r。

    每个下标最多入栈、出栈一次,所以总共有 O(n)O(n) 次区间加操作。

    线段树

    用线段树维护 f(l)f(l),支持:

    • 区间加;
    • 查询区间内最小值以及最小值出现的次数。

    因为 fr(l)≥0f_r(l)\ge 0 且 fr(r)=0f_r(r)=0,所以区间 [1,r][1,r] 的最小值一定是 00,最小值出现次数就是 fr(l)=0f_r(l)=0 的 ll 的个数,也就是以 rr 结尾的连续段数量。

    把每个 rr 的答案累加,就得到每个前缀的答案。

    正确性证明

    引理 1: 对任意 l≤rl\le r,fr(l)≥0f_r(l)\ge 0。

    子数组中有 r−l+1r-l+1 个互不相同的整数,全部在 [min⁡,max⁡][\min,\max] 中,因此区间 [min⁡,max⁡][\min,\max] 至少包含 r−l+1r-l+1 个整数,即 max⁡−min⁡+1≥r−l+1\max-\min+1\ge r-l+1。

    引理 2: 线段树在扫描到 rr 时,叶子 ll 的值恰好等于 fr(l)f_r(l)(对 l≤rl\le r)。

    对 rr 归纳。r=1r=1 时 f1(1)=0f_1(1)=0,初始值正确。从 r−1r-1 到 rr:

    • 长度项统一减 11;
    • 单调栈弹出一段时,这段左端点的最大值确实从 aidxa_{idx} 变为 ara_r,其余位置的最大值不变;
    • 最小值同理。 三类修改恰好覆盖 fr(l)−fr−1(l)f_r(l)-f_{r-1}(l) 的所有变化,因此归纳成立。

    引理 3: 扫描到 rr 时,[1,r][1,r] 中 fr(l)=0f_r(l)=0 的 ll 的个数等于以 rr 结尾的连续段数量。

    由 fr(l)=0f_r(l)=0 与连续段定义的等价性直接得到;又因为 fr(l)≥0f_r(l)\ge 0 且 fr(r)=0f_r(r)=0,区间最小值为 00,线段树返回的最小值个数正是零的个数。

    定理: 对每个前缀 kk,累加 r=1,…,kr=1,\dots,k 的答案,得到的就是前缀 kk 中所有连续段的数量。

    每个连续段有唯一的右端点 rr,按右端点分类计数再求和即可。

    复杂度

    每个下标最多入栈、出栈一次,线段树每次区间加/查询 O(log⁡n)O(\log n)。

    总时间复杂度 O(nlog⁡n)O(n\log n),空间复杂度 O(n)O(n)。

    参考代码(C++)

    #include <cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    struct SegTree {
        int n;
        vector<int> mn, cnt, lazy;
    
        SegTree(int n) : n(n), mn(4 * n + 5), cnt(4 * n + 5), lazy(4 * n + 5) {
            build(1, 1, n);
        }
    
        void build(int p, int l, int r) {
            cnt[p] = r - l + 1;
            mn[p] = 0;
            if (l == r) return;
            int mid = (l + r) >> 1;
            build(p << 1, l, mid);
            build(p << 1 | 1, mid + 1, r);
        }
    
        void apply(int p, int v) {
            mn[p] += v;
            lazy[p] += v;
        }
    
        void push(int p) {
            if (lazy[p]) {
                apply(p << 1, lazy[p]);
                apply(p << 1 | 1, lazy[p]);
                lazy[p] = 0;
            }
        }
    
        void pull(int p) {
            if (mn[p << 1] < mn[p << 1 | 1]) {
                mn[p] = mn[p << 1];
                cnt[p] = cnt[p << 1];
            } else if (mn[p << 1] > mn[p << 1 | 1]) {
                mn[p] = mn[p << 1 | 1];
                cnt[p] = cnt[p << 1 | 1];
            } else {
                mn[p] = mn[p << 1];
                cnt[p] = cnt[p << 1] + cnt[p << 1 | 1];
            }
        }
    
        void add(int ql, int qr, int v) { add(1, 1, n, ql, qr, v); }
    
        void add(int p, int l, int r, int ql, int qr, int v) {
            if (ql <= l && r <= qr) {
                apply(p, v);
                return;
            }
            push(p);
            int mid = (l + r) >> 1;
            if (ql <= mid) add(p << 1, l, mid, ql, qr, v);
            if (qr > mid) add(p << 1 | 1, mid + 1, r, ql, qr, v);
            pull(p);
        }
    
        pair<int, int> query(int ql, int qr) { return query(1, 1, n, ql, qr); }
    
        pair<int, int> query(int p, int l, int r, int ql, int qr) {
            if (ql <= l && r <= qr) return {mn[p], cnt[p]};
            push(p);
            int mid = (l + r) >> 1;
            if (qr <= mid) return query(p << 1, l, mid, ql, qr);
            if (ql > mid) return query(p << 1 | 1, mid + 1, r, ql, qr);
            auto L = query(p << 1, l, mid, ql, qr);
            auto R = query(p << 1 | 1, mid + 1, r, ql, qr);
            if (L.first < R.first) return L;
            if (L.first > R.first) return R;
            return {L.first, L.second + R.second};
        }
    };
    
    int main() {
        freopen("consecutive.in", "r", stdin);
        freopen("consecutive.out", "w", stdout);
    
        int n;
        if (scanf("%d", &n) != 1) return 0;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
        SegTree seg(n);
        vector<int> mxStack, mnStack;
        vector<long long> ans(n + 1);
        long long total = 0;
    
        for (int r = 1; r <= n; r++) {
            if (r > 1) seg.add(1, r - 1, -1);
    
            while (!mxStack.empty() && a[mxStack.back()] < a[r]) {
                int idx = mxStack.back();
                mxStack.pop_back();
                int left = mxStack.empty() ? 1 : mxStack.back() + 1;
                seg.add(left, idx, a[r] - a[idx]);
            }
            mxStack.push_back(r);
    
            while (!mnStack.empty() && a[mnStack.back()] > a[r]) {
                int idx = mnStack.back();
                mnStack.pop_back();
                int left = mnStack.empty() ? 1 : mnStack.back() + 1;
                seg.add(left, idx, a[idx] - a[r]);
            }
            mnStack.push_back(r);
    
            total += seg.query(1, r).second;
            ans[r] = total;
        }
    
        for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
        return 0;
    }
    

    易错点

    1. 查询区间必须是 [1,r][1,r],不能是 [1,n][1,n]:l>rl>r 的位置没有定义,线段树中仍为 00,如果查询整个数组会把它们错误地计入。
    2. 最小值个数只有在最小值为 00 时才有意义:代码依赖 fr(r)=0f_r(r)=0,所以区间最小值必为 00;若查询区间不含 rr,这个性质不成立。
    3. 单调栈的修改区间是 [p+1,idx][p+1,idx]:pp 是弹出后的新栈顶(空则为 00),不是 [idx,r][idx,r]。
    4. 长度项只对 [1,r−1][1,r-1] 减 11:l=rl=r 的新位置初始就是 00,不能一起减。
    5. 中间值可能暂时为负:先做 −1-1 再做最大值/最小值更新,更新过程中线段树可能出现负值,但查询发生在所有更新之后,最终 f≥0f\ge 0。
    6. 答案要用 long long:递增排列的答案为 n(n+1)2\frac{n(n+1)}{2},n=3×105n=3\times 10^5 时约为 4.5×10104.5\times 10^{10}。
    7. n=1n=1:答案为 11,代码自然处理。

    测试点设计

    测试点 设计意图
    1 样例 1,基本计数
    2 样例 2,前缀答案递增
    3 n=1n=1,答案为 11
    4 n=2n=2 的递减排列,答案为 1,31,3
    5 n=10n=10 的递增排列,答案为三角数
    6 n=10n=10 的递减排列,答案同样为三角数
    7 n=2000n=2000 的随机排列
    8 n=105n=10^5 的随机排列
    9 n=3×105n=3\times 10^5 的随机排列
    10 n=3×105n=3\times 10^5,由大量递增小块打乱而成,连续段数量较多
    11 n=3×105n=3\times 10^5 的“锯齿”排列 1,n,2,n−1,…1,n,2,n-1,\dots,答案恰为 2n−12n-1,检验边界
    12 n=3×105n=3\times 10^5 的递增排列,答案达到 n(n+1)2\frac{n(n+1)}{2},强制使用 long long
    • 1

    信息

    ID
    9
    时间
    2000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    2
    已通过
    2
    上传者