[codevs 1343] 蚱蜢(省队选拔赛湖南)

题解：

本题splay基本操作：

1.如果是左跳，比如从 x 左跳到 y，，就相当于查询 [ y, x ) 区间的最大值，那么就把 y-1 伸展到根，把 x 伸展到根的右节点，那么根的右节点的左节点对应的就是这段区间。

1.如果是右跳，比如从 x 右跳到 y，就相当于查询 ( x, y ] 区间的最大值，那么就把 x 伸展到根，把 y+1 伸展到根的右节点，那么根的右节点的左节点对应的就是这段区间。

3.这里 splay 是要将某个位置的节点伸展到给定位置，所以采用从顶向下查询第 rank 个的方式伸展，见代码。

4.remove操作：删除第 k 个，就把第 k-1 个伸展到根，把第 k+1 个伸展到根的右节点，删除它的左节点即可。别忘记 update 操作。

5.insert操作：如果要插到第 k 处，就把第 k-1 个节点旋转到根，把第 k 个节点旋转到根的右节点，那么插入到根的右节点的左节点就可以代替原来的第 k 个。好像没必要像我分两种情况。最后别忘 update，先子节点再根节点。

6.move操作：就是先 remove 再 insert。

7.宏定义：因为用到大量的根节点的左右节点的调用，而这里还不适合用引用，所以干脆定义了宏，简单清楚，编程效果好了很多。

8.边界防溢出：因为1、2中的将 y-1、y+1 伸展到根都是危险操作，因为 y 有可能等于 1 或 n，而 0 节点不能成为根节点，因为0节点默认为空；n+1 节点直接溢出，所以建立两个虚拟节点，一个为1，一个为 n+1，分别放在开头和末尾，对编程本身没影响，但不用担心溢出了，不过各个节点相应的位置就变了，读入位置 x 后 x++ 就行了。

代码：

总时间耗费: 6439ms总内存耗费: 3 kB

有些慢，但内存耗的很少。

#include<cstdio>#include<algorithm>using namespace std;const int INF = 1e9 + 7;const int maxn = 100000 + 10;int root, ch[maxn][2], v[maxn], s[maxn], maxv[maxn];void update(int o) {maxv[o] = max(v[o], maxv[ch[o][0]]);maxv[o] = max(maxv[o], maxv[ch[o][1]]);s[o] = s[ch[o][0]] + s[ch[o][1]] + 1;}int cmp(int o, int k) {int sum = s[ch[o][0]] + 1;if(sum == k) return -1;return k < sum ? 0 : 1;}void rotate(int& o, int d) {int k = ch[o][d^1]; ch[o][d^1] = ch[k][d]; ch[k][d] = o;update(o); update(k); o = k;}void splay(int& o, int k) {int d = cmp(o, k);if(d == -1) return;if(d == 1) k -= s[ch[o][0]] + 1;int p = ch[o][d];int d2 = cmp(p, k);int k2 = (d2 == 0) ? k : k – s[ch[p][0]] – 1;if(d2 != -1) {splay(ch[p][d2], k2);if(d2 == d) rotate(o, d^1); else rotate(ch[o][d], d);}rotate(o, d^1);}void build(int l, int r, int pa) {if(l > r) return;if(l == r) { maxv[l] = v[l]; s[l] = 1; if(l < pa) ch[pa][0] = l; else ch[pa][1] = l;return;} int m = (l+r) >> 1; maxv[m] = v[m];build(l, m-1, m); build(m+1, r, m); update(m);if(m < pa) ch[pa][0] = m; else ch[pa][1] = m;}#define lc ch[root][0]#define rc ch[root][1]void move(int x, int y) {splay(root, x-1); splay(rc, x-s[lc]); //x+1 – (s[lc]+1)int o = ch[rc][0];ch[rc][0] = 0; //removeupdate(rc);if(x < y) {splay(root, y-1); splay(rc, y-s[lc]-1); //y – (s[lc]+1)ch[rc][0] = o; update(rc); update(root); //notice} else {splay(root, y); splay(lc, y-1); //ch[lc][1] = o; update(lc); update(root);}}int main() {int n, m; scanf("%d%d", &n, &m); for(int i = 2; i <= n+1; i++) scanf("%d", &v[i]); build(1, n+2, 0); root = (n+3) >> 1;for(int i = 1; i <= m; i++) {int x, k; char cmd[1]; scanf("%d%s%d", &x, &cmd, &k); x++;switch(cmd[0]) {case 'L': {splay(root, x-k-1);splay(rc, x-s[lc]-1); //x – (s[lc]+1)printf("%d\n", maxv[ch[rc][0]]);move(x, x-k);break;}case 'D': {splay(root, x);splay(rc, x+k-s[lc]); //x+k+1 – (s[lc]+1)printf("%d\n", maxv[ch[rc][0]]);move(x, x+k);break;}}}return 0; }

穿越茫茫人海，寻找属于我们的那一份宁静。