题解：P9320 [EGOI 2022] Tourists / 乌托邦旅行团

有区间赋值操作考虑颜色段均摊。对每种颜色 $c$ 维护 $\operatorname{tag}_c$，再对每个位置 $i$ 维护一个 $b_i$，使得当前 $i$ 的真实值为 $b_i+\operatorname{tag}_{c_i}$，其中 $c_i$ 为 $i$ 当前的颜色。

对于一个颜色段 $(l,r,u)$，其颜色改变为 $v$ 后，还要使得真实值那个式子成立。考虑当前其真实值为 $b_i+\operatorname{tag}_{u}-\operatorname{dis}(u,v)$，我们要找到一个 $b'_i$ 使得 $b'_i+\operatorname{tag}_v=b_i+\operatorname{tag}_{u}-\operatorname{dis}(u,v)$，可得 $b'_i=b_i+\operatorname{tag}_u-\operatorname{dis}(u,v)-\operatorname{tag}_v$。所以要对 $b_i$ 进行区间加操作。

操作 e 直接在对应的 $\operatorname{tag}$ 上加即可。查询只需要支持单点查询 $b_i$ 和颜色。

上述操作可以使用 BIT 和 ODT 轻松实现。认为 $n,m,q$ 同阶，时间复杂度 $\mathcal{O}(n\log n)$，空间复杂度 $\mathcal{O}(n)$。