【算法随笔】P13983 数列分块入门 8

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

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

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

第二行输入 n 个数字，第 i 个数字为

a

i

a_i

ai​，以空格隔开。

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

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

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

题解

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

方法解析

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

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

时间复杂度分析：

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

细节补充说明