2025 河南省赛——Problem C. Toxel 与宝可梦图鉴（珂朵莉树+值域线段树维护全局信息）

2025 National Invitational of CCPC (Zhengzhou), 2025 CCPC Henan Provincial Collegiate Programming Contest

题目大意

给定一个长度为 $n$ 的数组 $a$，初始时第 $i$ 个位置的值为 $a_i$（$1 \le a_i \le n$）。共有 $m$ 次操作，每次操作给定 $l, r, d$，将区间 $[l, r]$ 内的值依次替换为 $d, d+1, \ldots, d+r-l$。

在初始状态以及每次操作后，输出数组中出现次数最多的值及其出现次数。若有多个值出现次数相同，输出其中编号最小的。

多组测试数据，$T$ 组，保证 $\sum n \le 2 \times 10^5$，$\sum m \le 2 \times 10^5$。

样例

输入：
3
3 3
1 2 3
1 1 2
2 2 3
3 3 1
1 1
1
1 1 1
8 8
7 6 6 4 3 8 5 3
4 4 4
6 8 6
1 1 7
4 7 4
6 7 6
2 7 5
1 5 7
1 6 8

输出：
1 1
2 2
3 2
1 1
1 1
1 1
3 2
3 2
6 3
6 3
6 3
6 3
7 2
8 2
8 2

样例解释（第一组数据）

初始数组为 $[1, 2, 3]$，三个值各出现 $1$ 次，输出最小编号 $1$，次数 $1$。

第 $1$ 次操作 $l=1, r=1, d=2$：将位置 $1$ 替换为 $2$，数组变为 $[2, 2, 3]$，值 $2$ 出现 $2$ 次最多，输出 $2\ 2$。

第 $2$ 次操作 $l=2, r=2, d=3$：将位置 $2$ 替换为 $3$，数组变为 $[2, 3, 3]$，值 $3$ 出现 $2$ 次最多，输出 $3\ 2$。

第 $3$ 次操作 $l=3, r=3, d=1$：将位置 $3$ 替换为 $1$，数组变为 $[2, 3, 1]$，三个值各出现 $1$ 次，输出最小编号 $1$，次数 $1$。

思路讲解

我看了一下，宝可梦这道题目珂朵莉树不会被卡的原因是因为全局查询，可以通过维护全局信息解决这个问题。
好像只要改成区间查询，区间修改，珂朵莉树一定会被卡。

珂朵莉树的时间复杂度过于玄学了，我还是想用这个时间复杂度更加确定的算法解决问题。

AC代码

源代码

心路历程（WA，TLE，MLE……）