题解：
本题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#include 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; //remove update(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; }