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

lzyqwq · 2025-11-26 16:24:42 · 题解

有区间赋值操作考虑颜色段均摊。对每种颜色 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)。