警告

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

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

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

点击屏幕以关闭。

「SPOJ TTM」To the moon - 主席树

题意

传送门:SPOJ TTM - To the moon

本题 AC 时间 190314,难度较低,见谅。

维护一个序列,支持区间加、区间和、历史区间和、版本回退。

\(1\le n,m\le10^5\)

解法

一个非常显然的想法是标记永久化主席树,但是我不想写

还有一个方法,就是用两棵 BIT 维护区间加区间和。

但是 BIT 不能持久化,于是写两棵单点修改区间查询的线段树就好了。

复制粘贴,双倍快乐

代码