CF896C Willem, Chtholly and Seniorious 题解 / ODT 学习笔记

zrl123456 · 2025-10-23 13:56:19 · 题解

:::::info[题目基本信息] 考察：颜色段均摊（珂朵莉树 ODT）（2600）。
题目简介：
给定序列 \{a_n\}，你需要进行 q 次共四种操作：

1. 给定 l,r,x，进行操作 \forall i\in[l,r],a_i\leftarrow a_i+x。
2. 给定 l,r,x，进行操作 \forall i\in[l,r],a_i\leftarrow x。
3. 给定 l,r,x，求 x\text{thmin}_{i=l}^r(a_i)。
4. 给定 l,r,x,y，求 \displaystyle(\sum_{i=l}^ra_i^x)\bmod y。

数据范围：

• 对于所有操作，1\le l\le r\le n。
• 对于 3 操作，1\le x\le r-l+1。
• 对于 1,2,4 操作，1\le x\le 10^9。
• 对于 4 操作，1\le y\le 10^9。
• 保证数据随机。

时间限制：2s。
空间限制：250MB。
::::: ODT 板子题，直接上讲解。
:::::success[ODT 讲解] ODT 由 lxl 发明，在该题诞生，是一种专门处理随机数据且包含覆盖操作的一种暴力数据结构。
我们考虑维护一些连续段，每个连续段内的数都相同，由于本题有比较多的覆盖操作，所以期望复杂度是有保证的。
我们只需要用 set 维护连续段即可。
::::: 然后这道题直接维护即可。
重点在代码。

code