懒得打代码了,口胡一下这道题。
不难发现,去掉 Rotate
和 Flip
操作后这就是一个裸线段树了。
翻转项链难以维护,那我们就改为翻转序号。Origin
:Flip
:Rotate 3
:
可以证明这样操作不会影响正确性。
抽象化操作,发现 Flip
就是把除了 \(1\) 以外的所有序号 \(i\) 变为 \(n - i + 2\),Rotate
就是把一部分序号 \(i\) 变为 \(i - k\),一部分变为 \(i - k + 1\)。这样一来,显然就可以用线段树维护序号了。
两个线段树,一个加乘线段树用于维护 Flip
和 Rotate
对序号产生的影响,一个色块线段树维护区间块数。
相关文章
- 03-08LOJ 2353 & 洛谷 P4027 [NOI2007]货币兑换(CDQ 分治维护斜率优化)
- 03-08洛谷 P4130 [NOI2007]项链工厂
- 03-08洛谷 P1063 能量项链
- 03-08洛谷1972 HH的项链 树状数组查询区间内不同的数的数量
- 03-08【洛谷】P1972 [SDOI2009]HH的项链 (树状数组)
- 03-08洛谷 P1972 [SDOI2009]HH的项链
- 03-08[洛谷P1972][题解][SDOI2009]HH的项链
- 03-08洛谷 P1972 BZOJ 1878 [SDOI2009]HH的项链
- 03-08洛谷 P1972 [SDOI2009]HH的项链【莫队算法学习】
- 03-08化工厂装箱员(洛谷 P2530)