这个是个裸的区间染色段数均摊 考虑维护每个点与其颜色相同的前驱 用平衡树维护颜色连续段,然后考虑一个颜色连续段里面除了第一个点以外,后面的点i的前驱都是i-1 用树套树/分治维护,于是这个颜色段的变化可以O( log^2n )维护 总复杂度O( (n+m)log^2n )
注意常数… 小心细节…
注册一个 云斗学院 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 云斗学院 通用账户