HDU 1890 Robotic Sort (Splay)

HDU 1890 Robotic Sort (Splay)

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

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日 2,057
  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40