洛谷P13983 数列分块入门 8
题目背景
洛谷的数列分块入门系列的测试数据范围和原题有不同。

题目描述
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 c。

输入格式
第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 $a_i$，以空格隔开。

接下来输入 n 行询问，每行输入三个数字 l、r、c，以空格隔开。

表示先查询位于 [l,r] 的数字有多少个是 c，再把位于 [l,r] 的数字都改为 c。

输出格式
对于每次询问，输出一行一个数字表示答案。

题解

这道题非常适合使用珂朵莉树(Chtholly Tree，又称 ODT - Old Driver Tree)来解决。

方法解析

珂朵莉树是一种基于 std::set 维护区间的数据结构。它将值相同的连续一段元素合并成一个区间（节点）进行维护。对于一般的区间操作，如果操作中包含高频的区间推平（区间赋值）操作，珂朵莉树能展现出极高的效率。

这道题的每一个操作恰好都是：先查询区间内具有某个值的元素个数，然后立刻把这个区间的所有元素全部修改为这个值（即典型的“区间推平”）。

时间复杂度分析：

1. 每次操作最多引入 $2$ 个新的区间切割点（分别在 $l$ 和 $r+1$ 处）。
2. 在处理了最多 $O(n)$ 次切割后，每次的推平操作会把 $[l,r]$ 内的所有散乱区间全部删除，替换为仅仅 $1$ 个大区间。
3. 因为新产生的区间总数是 $O(n)$ 级别的，每个区间被加入 set 和从 set 中删除最多各一次，所以整体的均摊时间复杂度被严格保证在 $O(n\log n)$，足以在时限内轻松通过 $n=300000$ 的数据。

C++ 完整代码

#include <iostream>
#include <set>

using namespace std;

// 定义珂朵莉树的节点
struct Node {
    int l, r;
    mutable long long v; // mutable 允许在 set 迭代器中修改值，虽然本题直接erase再insert
    Node(int l, int r = -1, long long v = 0) : l(l), r(r), v(v) {}
    // set 根据左端点排序
    bool operator<(const Node& o) const {
        return l < o.l;
    }
};

set<Node> odt;
int n;

// 分裂操作：将包含 pos 的区间 [l, r] 分裂为 [l, pos-1] 和 [pos, r]
// 并返回指向 [pos, r] 的迭代器
set<Node>::iterator split(int pos) {
    if (pos > n) return odt.end(); // 超出边界返回 end()
    
    auto it = odt.lower_bound(Node(pos));
    if (it != odt.end() && it->l == pos) {
        return it; // 如果已经存在以 pos 为左端点的区间，直接返回
    }
    
    --it; // 否则 pos 必然被包含在它前一个区间内部
    int l = it->l, r = it->r;
    long long v = it->v;
    
    // 删除原区间，插入两个分裂后的区间
    odt.erase(it);
    odt.insert(Node(l, pos - 1, v));
    return odt.insert(Node(pos, r, v)).first;
}

int main() {
    // 开启 Fast IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n)) return 0;

    // 初始输入压缩连续相同元素，优化初始化耗时
    long long prev_a = 2e18; // 使用超出数据范围的 dummy 值
    int prev_l = 1;
    
    for (int i = 1; i <= n; ++i) {
        long long a;
        cin >> a;
        if (i == 1) {
            prev_a = a;
            prev_l = 1;
        } else if (a != prev_a) {
            odt.insert(Node(prev_l, i - 1, prev_a));
            prev_a = a;
            prev_l = i;
        }
    }
    if (n >= 1) {
        odt.insert(Node(prev_l, n, prev_a));
    }

    // 处理每次询问与修改
    for (int i = 0; i < n; ++i) {
        int l, r;
        long long c;
        cin >> l >> r >> c;
        
        // 核心：必须先 split 右端点 (r + 1)，再 split 左端点 (l)
        // 顺序不能反，否则 split 右端点可能会导致左端点的迭代器失效
        auto itr = split(r + 1);
        auto itl = split(l);
        
        int count = 0;
        // 统计查询区间内值为 c 的元素个数
        for (auto it = itl; it != itr; ++it) {
            if (it->v == c) {
                count += (it->r - it->l + 1);
            }
        }
        
        // 区间推平（赋新值）：删除散段，插入整段
        odt.erase(itl, itr);
        odt.insert(Node(l, r, c));
        
        cout << count << "\n";
    }

    return 0;
}

细节补充说明

1. 为什么要先 split(r+1) 再 split(l)？
   在向集合请求分离时，如果先 split(l) 会返回一个迭代器，接下来做 split(r+1) 可能会因为恰巧在同一个大块内部而把包含 $l$ 的区间直接从 set 中 erase 删除掉，导致最初取得的 $l$ 的迭代器失效进而引发内存段错误（RE）。按倒序分裂（先右后左）就能安全规避此问题。
2. 数据类型界限：
   题目给出元素的值在 $-2^{31}$ 到 $2^{31}-1$ 内，这其实恰好填满标准有符号 32位整型（int）的范围。但为确保计算和逻辑绝对安全避免溢出（以及设定不可能达到的界限哨兵值 2e18），代码采用的 long long 存储元素值。由于只计个数，count 最多为 300,000 不会越过 int，因此统计个数放心使用 int。