题解：P13983 数列分块入门 8

· · 题解

题解：P13983 数列分块入门 8

分块入门题？珂朵莉树模板题！

图解珂朵莉树

珂朵莉树本质是比较暴力的。

珂朵莉树将每个颜色段以 (l,r,x) 的方式存储，意思是区间 [l,r] 只有一种颜色 x。

每次区间颜色段覆盖将 [l,r] 都染成 x 时，我们将 l 和 r 所在的颜色段分裂开，再将夹在 l 所在颜色段到 r 所在颜色段间的所有颜色段删除，插入颜色段 (l,r,x)。

这就是珂朵莉树实现颜色段覆盖的原理。

时间复杂度

可以证明随机数据下，每次询问均摊颜色段个数仅有 \log n 个。

对于每次 split 操作会增加一个颜色段；对于每次 assign 会最多增加 O(1) 个颜色段，删除最多 (n) 个颜色段，但事实上经过研究分析只会有 O(\log n) 个颜色段，珂朵莉树时间复杂度保证就在推平操作。

假设每次操作是随机的，那么 l 和 r 均匀分布，一个点 j 成为端点的概率 p_j 满足：p_j \approx \left( \frac{(j-1)^2 + (n-j)^2}{n^2} \right)^n 。

对所有点求和：\frac{1}{n} \sum_{j=1}^n p_j = O\left(\frac{1}{n}\right) 表示平均一个端点存活概率随操作次数增加而快速下降。

所以总端点数约为 O(n)，但由于随机覆盖，大部分会被合并掉。

仅少数端点幸存，根据积分估计：E_{t} = O\left(\frac{n}{n} + \log n\right) = O(\log n) 。

当结论记就好了。

code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, x, l, r, c;
struct odt {
    int l, r; mutable int x;
    // mutable 关键字可以让我们直接修改 set 中的 odt 的 x 。
    friend bool operator < (odt a, odt b) {
        return a.l < b.l;
        // 按顺序排序区间
    }
}; set <odt> s;
auto split(int pos) {
    auto it = s.lower_bound({pos, 0, 0});
    if (it != s.end() && it -> l == pos) return it;
    if ((--it) -> r < pos) return s.end();
    int l = it -> l, r = it -> r, v = it -> x;
    s.erase(it); s.insert({l, pos - 1, v});
    return s.insert({pos, r, v}).first;
}
/*
会将下标 pos 所在颜色段 (l,r,x) 分为
(l,pos-1,x) 和 (pos+1,r,x) 两个颜色段，
并返回 (pos+1,r,x) 在 set 中的位置（迭代器）。
*/
inline void assgin(int l, int r, int x) {
    auto R = split(r + 1), L = split(l);
    // L 是以 l 开头的颜色段
    // R 是以 r+1 开头的颜色段
    s.erase(L, R); s.insert({l, r, x});
    // 删除了 set 中 [L, R) 的颜色段
    return;
}
int query(int l, int r, int x, int cnt = 0) {
    auto R = split(r + 1), L = split(l);
    for (; L != R; L++) {
    //遍历颜色段
        if (L -> x == x) {
            cnt += L -> r - L -> l + 1;
            //如果当前颜色段颜色是要查询的颜色，答案加上颜色段长度
        }
    }
    return cnt;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        s.insert({i, i, x});
    }
    for (int i = 1; i <= n; i++) {
        cin >> l >> r >> c;
        cout << query(l, r, c) << '\n';
        assgin(l, r, c);
    }
    return 0;
}

本文写于 2025 年 9 月 7 日，数列分块入门没有分块标签，但是有珂朵莉树标签，烟斗不演了！