Splay

题目链接：点我~~ 题意：给定n个数，有两种操作区间切割和区间翻转，求m次操作后的序列。 思路：对于区间切割，先将[l,r]取出来，再合并到c到c+1之间。(区间切割，区间翻转) #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsig...

题目链接：点我~~ 题意：n个数排成一列，每次选择序列中的最小值（如果有多个，取原始位置最小的），把它和它前面的所有数翻转，然后把这个数从序列中删去。输出每次选择的最小值的下标。 思路：每次找到值之后，旋转到根节点，左子树的size可以知道所求的下标，然后删除根节点，再旋转左区间。其中使用lazy标记标记所需翻转的区间。(区间翻转，删除根节点) #inclu...

题目链接：点我~~ 题意：给n个数，有两种操作，一种是查询区间和，另一种是在区间上每一个数加上v。 思路：第一次摸splay tree，这题算是个模板题，适合思考人生。。。 //Splay(x,0); 将x变为跟节点 //Splay(x,root); 将x变为root下的节点  维护区间时通常旋转为root的右子树 //所需要维护的区间[l，r]，通过旋转后...