给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个数旋转到根的右孩子， 但是却没有这两个数。 所以为了方便，在序列的两端加上两个数，这两个数比序列中的所有数都小， 所以并不影响答案。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = + ;
int next[N][],pre[N],key[N],Max[N],sz[N],tot,root;
int a[N]; //如果更新第x个结点， 那么将第该结点splay到根，然后更新
/*
如果询问区间[a,b]的最大值， 那么将a-1 splay到root，将b+1旋到next[root][1] */
void newNode(int &rt, int fa, int k)
{
rt = ++tot;
next[rt][] = next[rt][] = ;
sz[rt] = ;
pre[rt] = fa;
key[rt] = k;
Max[rt] = k;//???????
}
void maintain(int rt)
{
Max[rt] = std::max(key[rt], std::max(Max[next[rt][]],Max[next[rt][]]));
sz[rt] = sz[next[rt][]] + sz[next[rt][]] + ;
}
void build(int &rt, int fa, int l, int r)
{
if(l>r) return;
int m =(l+r)>>;
newNode(rt,fa,a[m]);
build(next[rt][],rt,l,m-);
build(next[rt][],rt,m+,r);
maintain(rt);
}
void rotate(int x, int kind)
{
int y = pre[x];
next[y][!kind] = next[x][kind];
maintain(y);
pre[next[x][kind]] = y;
if(pre[y])
next[pre[y]][next[pre[y]][]==y] = x;
pre[x] = pre[y];
next[x][kind] = y;
pre[y] = x;
maintain(x);
}
int kth(int x, int k)
{
int tmp = sz[next[x][]] + ;
if(tmp==k)
return x;
if(tmp > k)
return kth(next[x][],k);
return kth(next[x][],k-tmp);
}
void splay(int x, int goal)
{
/*
只考虑左右旋的splay
while(pre[x]!=goal)
{
if(next[pre[x]][0]==x)
rotate(x,1);
else
rotate(x,0);
}
*/
while(pre[x]!=goal)
{
int y = pre[x];
if(pre[y]==goal)
{
if(next[y][]==x)
rotate(x,);
else
rotate(x,);
}
else
{
//kind 表示y是父亲的哪个儿子, 0 左，1 右
int kind = next[pre[y]][]==y;
if(next[y][kind]==x)//共线
{
rotate(y,!kind);
rotate(x,!kind);
}
else
{
rotate(x,kind);
rotate(x,!kind);
}
}
}
if(goal==)
root = x;
}
int main()
{
int n,m;
char opt[];
int x,y;
while(scanf("%d%d",&n,&m)!=EOF)
{
tot = ;
memset(next,,sizeof(next));
for(int i=;i<=n;++i)
scanf("%d",&a[i]);
newNode(root,,-);
newNode(next[root][],root,-);
build(next[next[root][]][],next[root][],,n);
maintain(next[root][]);
maintain(root);
while(m--)
{
scanf("%s%d%d",opt,&x,&y);
if(opt[]=='Q')
{
int tmp = kth(root,x);
splay(tmp,);
splay(kth(root,y+),root);
printf("%d\n",Max[next[next[root][]][]]);
}
else
{
splay(kth(root,x+),);
key[root] = Max[root] = y;
maintain(root);
}
}
}
return ;
}