25
2016-09
2016-09
![HDU 3487 Play with Chain (Splay)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 3487 Play with Chain (Splay)
题目链接:点我~~
题意:给定n个数,有两种操作区间切割和区间翻转,求m次操作后的序列。
思路:对于区间切割,先将[l,r]取出来,再合并到c到c+1之间。(区间切割,区间翻转)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsig...
09月25日
1,875
25
2016-09
2016-09
![HDU 1890 Robotic Sort (Splay)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 1890 Robotic Sort (Splay)
题目链接:点我~~
题意:n个数排成一列,每次选择序列中的最小值(如果有多个,取原始位置最小的),把它和它前面的所有数翻转,然后把这个数从序列中删去。输出每次选择的最小值的下标。
思路:每次找到值之后,旋转到根节点,左子树的size可以知道所求的下标,然后删除根节点,再旋转左区间。其中使用lazy标记标记所需翻转的区间。(区间翻转,删除根节点)
#inclu...
09月25日
2,024
25
2016-09
2016-09
![POJ 3468 A Simple Problem with Integers (Splay)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
POJ 3468 A Simple Problem with Integers (Splay)
题目链接:点我~~
题意:给n个数,有两种操作,一种是查询区间和,另一种是在区间上每一个数加上v。
思路:第一次摸splay tree,这题算是个模板题,适合思考人生。。。
//Splay(x,0); 将x变为跟节点
//Splay(x,root); 将x变为root下的节点 维护区间时通常旋转为root的右子树
//所需要维护的区间[l,r],通过旋转后...
09月25日
1,967