给n个数，有两种操作 Q a b 询问区间[a,b]的最大值， U a b 将第a个数的值改成b
splay树的中序遍历是我们所维护的序列。如果要询问区间[a,b]的最大值，那么只要将第a-1个数旋转到根结点， 将第b+1个数旋转到根的右孩子，那么根的右孩子的左子树就是所要查询的区间。我们为每一个结点维护一个最大值，表示该以该结点为根的子树的最大值， 那么答案就是 Max[next[next[root][1]][0]];
为了防止越界， 比如要查询区间[1,n] 那么要将第0个数旋转到根结点，将第n+1个数旋转到根的右孩子， 但是却没有这两个数。 所以为了方便，在序列的两端加上两个数，这两个数比序列中的所有数都小， 所以并不影响答案。
1 #include2 #include 3 #include 4 #include 5 const int N = 200000 + 10; 6 int next[N][2],pre[N],key[N],Max[N],sz[N],tot,root; 7 int a[N]; 8 9 //如果更新第x个结点， 那么将第该结点splay到根，然后更新 10 /* 11 如果询问区间[a,b]的最大值， 那么将a-1 splay到root，将b+1旋到next[root][1] 12 13 */ 14 void newNode(int &rt, int fa, int k) 15 { 16 rt = ++tot; 17 next[rt][0] = next[rt][1] = 0; 18 sz[rt] = 1; 19 pre[rt] = fa; 20 key[rt] = k; 21 Max[rt] = k;//??????? 22 } 23 void maintain(int rt) 24 { 25 Max[rt] = std::max(key[rt], std::max(Max[next[rt][0]],Max[next[rt][1]])); 26 sz[rt] = sz[next[rt][0]] + sz[next[rt][1]] + 1; 27 } 28 void build(int &rt, int fa, int l, int r) 29 { 30 if(l>r) return; 31 int m =(l+r)>>1; 32 newNode(rt,fa,a[m]); 33 build(next[rt][0],rt,l,m-1); 34 build(next[rt][1],rt,m+1,r); 35 maintain(rt); 36 } 37 void rotate(int x, int kind) 38 { 39 int y = pre[x]; 40 next[y][!kind] = next[x][kind]; 41 maintain(y); 42 pre[next[x][kind]] = y; 43 if(pre[y]) 44 next[pre[y]][next[pre[y]][1]==y] = x; 45 pre[x] = pre[y]; 46 next[x][kind] = y; 47 pre[y] = x; 48 maintain(x); 49 } 50 int kth(int x, int k) 51 { 52 int tmp = sz[next[x][0]] + 1; 53 if(tmp==k) 54 return x; 55 if(tmp > k) 56 return kth(next[x][0],k); 57 return kth(next[x][1],k-tmp); 58 } 59 void splay(int x, int goal) 60 { 61 /* 62 只考虑左右旋的splay 63 while(pre[x]!=goal) 64 { 65 if(next[pre[x]][0]==x) 66 rotate(x,1); 67 else 68 rotate(x,0); 69 } 70 */ 71 while(pre[x]!=goal) 72 { 73 int y = pre[x]; 74 if(pre[y]==goal) 75 { 76 if(next[y][0]==x) 77 rotate(x,1); 78 else 79 rotate(x,0); 80 } 81 else 82 { 83 //kind 表示y是父亲的哪个儿子, 0 左，1 右 84 int kind = next[pre[y]][1]==y; 85 if(next[y][kind]==x)//共线 86 { 87 rotate(y,!kind); 88 rotate(x,!kind); 89 } 90 else 91 { 92 rotate(x,kind); 93 rotate(x,!kind); 94 } 95 } 96 } 97 if(goal==0) 98 root = x; 99 }100 int main()101 {102 int n,m;103 char opt[3];104 int x,y;105 while(scanf("%d%d",&n,&m)!=EOF)106 {107 tot = 0;108 memset(next,0,sizeof(next));109 for(int i=1;i<=n;++i)110 scanf("%d",&a[i]);111 newNode(root,0,-1);112 newNode(next[root][1],root,-2);113 build(next[next[root][1]][0],next[root][1],1,n);114 maintain(next[root][1]);115 maintain(root);116 while(m--)117 {118 scanf("%s%d%d",opt,&x,&y);119 if(opt[0]=='Q')120 {121 int tmp = kth(root,x);122 splay(tmp,0);123 splay(kth(root,y+2),root);124 printf("%d\n",Max[next[next[root][1]][0]]);125 }126 else127 {128 splay(kth(root,x+1),0);129 key[root] = Max[root] = y;130 maintain(root);131 }132 }133 }134 return 0;135 }