总结题前,先上三份平衡树代码
spaly
1 |
|
treap
1 |
|
FHQ treap
1 |
|
P2234 [HNOI2002]营业额统计
题目大意是让你求出每天营业额和之前的营业额的最小差值,然后求和。
很容易会想到平衡树,找出每一天营业额的前驱和后继,取两者和当天的值的最小差值即可。
代码:
1 |
|
然而我的splay被玄学的卡了一个点,郁闷ing
P3391 【模板】文艺平衡树(Splay)
题意极其简单:翻转区间。然而题却不好想。
我们用splay来维护序列的顺序,splay中排名第k的节点在序列中就是第k个。所以无论我们怎么旋,当前splay所维护的序列顺序是不变的。然后我们考虑翻转。这里有一个神奇的操作,找出l的前驱x和r的后继y,splay(x,0),splay(y,x)。此时y的左儿子及其子树便是区间l到r。我们只需像线段树一样将节点打上标记即可。pushdown时传递标记并交换它的左右儿子。输出按中序遍历即可。
上代码:
1 |
|
其中有几点需要注意:
这道题中节点并没有权值,所以不能用权值判断左右儿子。
因为有时你要翻转1到n的序列,所以你可以建n+2各节点,第n号节点表示在序列中的n-1的位置。
P1486 [NOI2004]郁闷的出纳员
这道题的难点主要是之前的每个员工加上了某个工资,然而新加入的员工并不会加上,此时打一个标记显然不行。这是我们可以将新加入的员工工资减去之前员工加过的工资。
看代码:
1 |
|
还是被卡一个点,90分也许treap能过吧。
P4146 序列终结者
这道题并不算太难,可以当做splay的模板题。从这道题你可以体会到splay中标记的妙用。
1 |
|
P2042 [NOI2005]维护数列
这道题是上一道题的升级版,需要你来实现六种操作,核心还是split函数,第六个操作稍微难想一点,求一个序列的最长连续子串可以用归并的思想,然后通过update来更新。
这道题的细节太多了:
- 在翻转区间的时候,$tr[x].l$和$tr[x].r$需交换值。($tr[x].l$表示区间从左端点开始连续最大子串和。tr[x].r同理)
- 修改操作中不能用tr[x].tag记录修改后的值,因为可以将其修改为0,只能用它记录是否被修改。
- update的时间,update应在每次更改一个节点的子树后进行,在本题中,应在rotate,MAKE_SAME,REVERSE,DELETE,INSERT,所有的修改操作最后update。
- pushdown只需在kth函数中进行即可。
- 不要忘记给tr[x].l和tr[x].r,tr[x].dp赋初值。
看代码
1 |
|
本文作者:
syrsteven
最后更新: 2023年09月02日 04:06:21
本文链接: http://syrsteven.github.io/post/922e70da.html
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可,转载请注明出处!
最后更新: 2023年09月02日 04:06:21
本文链接: http://syrsteven.github.io/post/922e70da.html
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可,转载请注明出处!