警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「洛谷 P5350」序列 - ODT

这又是一篇水 Blog。

题意

传送门:洛谷 P5350 - 序列

维护一个序列,支持区间和、区间覆盖、区间加、区间复制、区间交换和区间翻转。模 \(10^9+7\)

\(1\le n,m\le3\times10^5,0\le a_i,v<10^9+7\)保证数据随机

解法

因为数据随机,所以可以写 ODT。或者你也可以用任何一种复杂度正确的平衡树。

写 ODT 的时候注意一个坑:std::setinsert 时迭代器不会失效,但是在 erase 时迭代器会失效

所以 split 完后需要重新用 lower_bound 定位,而且 copy, swap, rev 操作时需要用一个 vector 暂存。

代码