3139. [HSOI 2019] HS的新题 - COGS

显然随机数据, 考虑珂朵莉树.

以下均在 auto itr = split(r + 1), itl = split(l);的基础上进行.

注意要开 long long, 以及, 所有操作后得到的答案均为模运算后结果, 否则这个题写不成.

操作 1

直接 assign 即可.

操作 2

遍历 $itl \le it <itr$, 用逆元计算每一个颜色段 $/x$ 的值即可.

操作 3

遍历 $itl \le it <itr$, 计算每一个颜色段 $*x$ 即可.

操作 4

遍历 $itl \le it <itr$, 如果 $x \le v \le y$, then cnt++.

操作 5

遍历 $itl \le it <itr$, 统计总和, 再 assign 平均值即可.

操作 6

遍历 $itl \le it <itr$, map 统计每个数个数, 再遍历一遍 map 即可.

操作 7

遍历 $itl \le it <itr$, 全部数字插入到一个 set 中, set 的值就是答案.

操作 8

遍历 $itl \le it <itr$, 使用异或空间线性基处理即可.