标签:splay

【算法】 Splay 伸展树 总结

Splay 伸展树

by 蒟蒻XZY 2017.12.28

-1. 注

以下用数组模拟链表,不用指针。

未说明的情况下定义的节点结构体为:

[crayon-5a5f0b95bbdfd15[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 [Scoi2013]多项式的运算 splay BZOJ – 3323 LUOGU – 3278

1. 题目

2. 题解

可以说这题令我非常angry。。。

其实不难,就一个splay区间加[......]

[继续阅读= ̄ω ̄=]

Read MoreView 4 Comments

【题解】 二逼平衡树 树套树(线段树套splay) BZOJ – 3196

1. 题目

传送门= ̄ω ̄=

2. 题解

感觉就是Dynamic Rankings那题的加强版。

还是老样子搞个线段树套splay就行了,具体解法见我写的那个Dynamic Rankings的[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 Dynamic Rankings 动态区间第k小问题 二分答案+树套树(线段树套splay) BZOJ – 1901

1. 题目

传送门= ̄ω ̄=

更新:突然发现LUOGU上有这题(LUOGU - 2617),可以木有权限号刷~传送门= ̄ω ̄=

题目大意:

给你一个序列,要求资磁两个操作:

  • 将某一个位置的[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 supermemo splay POJ – 3580 BZOJ – 1895

1. 题目

传送门= ̄ω ̄=

2. 题解

考试考了这题,幸好对拍了。

挺好的模板。

代码:

Read MoreView 2 Comments

【题解】 Editor splay BZOJ – 1507

1. 题目

传送门= ̄ω ̄=

2. 题解

//一开始一遍写完一遍编译通过,然后觉得可能有问题就手写了一下题目描述中的样例,结果发现程序不出结果,调了20分钟。。。最后发现程序没问题,是自己样例写[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 郁闷的出纳员 splay BZOJ – 1503

1. 题目

传送门= ̄ω ̄=

2. 题解

好吧其实我知道可以不写push_down直接记录当前更改总量的。

但是为了练习splay,也就打了带下穿标记的啦= ̄ω ̄=

但是,,,气死我惹!!![......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 维修数列 splay BZOJ – 1500

1. 题目

传送门= ̄ω ̄=

大概就是这样:

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

2. 题解

丧心病狂の模板题,,,

mmp调了我三天

主要是这题细节好多的,[......]

[继续阅读= ̄ω ̄=]

Read MoreView 1 Comment

【题解】 序列终结者 splay BZOJ – 1251

1. 题目

传送门= ̄ω ̄=

此题貌似是个权限题,上面那个传送门是到我的BZOJ离线题库里的,可以看题但不能提交。如果没权限号的话可以搞标程(比如我的代码哈哈哈)对拍。

不过我还是复制一下题面吧[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 文艺平衡树 splay BZOJ – 3223

1. 题目

传送门= ̄ω ̄=

题目大意:

给你一个长度为$n$的序列,还有$m$个操作,每次操作给出区间$[l,r]$,表示将该区间内的数字反转(比如123变成321),求所有操作后的序列。[......]

[继续阅读= ̄ω ̄=]

Read MoreView 1 Comment