【题解】Ynoi2010 Brodal queue 分块 — Qiuly

本题不弱于小 Z 的袜子，考虑分块，令 $B$ 为块数。

先考虑单点修改，可以令 $f(x,y)$ 表示从块 $x$ 中选出一个数，然后从块 $y$ 中选出同样的数的方案数，放到平面上，有值的地方就是一个三角形，询问也是询问一个三角形中的 $f(x,y)$ 和。

怎么做修改，对每个颜色维护一个前缀出现次数和，然后就可以快速计算贡献了。注意到如果修改的点属于块 $x$，影响的 $f(x,y)$ 是呈 “L” 状，且拐点一定顶到 $y=x$ 这条线。所以修改能拆成 “ 一行 + 拐点 + 一列” 的形式，拐点单独维护（即同一块内的贡献），行和列分开维护，做前缀和，询问的时候分别查询行和列即可。

此时取块大小 $B=\sqrt{n}$，时间复杂度为 $O(n\sqrt{n})$ 。

接下来考虑做原问题，即将单点修改变成区间染色。区间染色的常用套路是颜色段均摊。考虑在每个块内压缩所有的颜色段，表示成若干数对 $(c,t)$ 的形式（$c$ 指颜色编号，$t$ 指颜色段长度），同样讨论修改：

• 散块：暴力重构，将区间覆盖后可能消失的段删除贡献，然后暴力做区间覆盖重建颜色段结构，再考虑原来删除贡献的位置对应的新段的贡献。这里细节有点多。

  不难发现等价于普通序列上的颜色段均摊，暴力删除 / 重建的段数是 $O(\frac{n}{B}+m)$ 的（注意到对散块的修改总量是 $O(m)$ 的）。同时删除 / 加入段后更新 $f(x,y)$ 的方法和单点修改部分没有区别，单次修改仍然为 $O(B)$ 。

• 整块：区间染色时跨过的整块不可能每次暴力更新 $f(x,y)$，不过可以注意到此时整段都是一个颜色。不妨在整块被染成同一颜色时（之前仍然有若干颜色段），暴力删除之前的所有颜色段的贡献，并且在查询的时候单独处理整块。

  注意到整块染色，删除之前所有颜色段这一操作仍然可以套用颜色段均摊的复杂度分析方法。同时询问暴力计算整块的贡献，和暴力计算散点的贡献几乎没有区别，可以轻松算出。

仍然考虑取 $B=\sqrt{n}$（当然可以因常数原因微调），时间复杂度为 $O((n+m)\sqrt{n})$ 。

看起来我是 sb，对拍的时候一定要多调调块大小啊 >_<

代码：记录详情 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)