1. 题目

传送门= ̄ω ̄=

大概就是这样:

需要每单个操作(插入、删除算多次操作)$log_2N$以下

2. 题解

丧心病狂の模板题,,,

mmp调了我三天

主要是这题细节好多的,比如要注意翻转儿子要先下传再打标记(和我以前做法不同)。

具体做法就和线段树(静态)的做法一样,维护左右最大的两边连续区间和,这样就能获得一个子树对应的区间中的最大子段和。我就不做过多赘述了(懒)

总之是个练splay的好题啊,再次刷新我打splay的方法。

代码: