洛谷 P4130 [NOI2007]项链工厂

懒得打代码了,口胡一下这道题。
不难发现,去掉 RotateFlip 操作后这就是一个裸线段树了。
翻转项链难以维护,那我们就改为翻转序号。
Origin
洛谷 P4130 [NOI2007]项链工厂
Flip
洛谷 P4130 [NOI2007]项链工厂
Rotate 3
洛谷 P4130 [NOI2007]项链工厂
可以证明这样操作不会影响正确性。
抽象化操作,发现 Flip 就是把除了 \(1\) 以外的所有序号 \(i\) 变为 \(n - i + 2\),Rotate 就是把一部分序号 \(i\) 变为 \(i - k\),一部分变为 \(i - k + 1\)。这样一来,显然就可以用线段树维护序号了。
两个线段树,一个加乘线段树用于维护 FlipRotate 对序号产生的影响,一个色块线段树维护区间块数。

上一篇:原生js是实现一个简单的时钟(transform属性)


下一篇:CSS3属性transform