线段树的水题，拿来学习一下splay.
本题涉及到求最大值以及单点更新，折腾了许久，差不多把splay搞明白了。
按位置建树，按位置是一颗排序二叉树，对于区间的操作非常方便，每次操作都将需要的结点转自根的右孩子的左孩子，因为加了2个结点，一个最小的，一个最大的，据说是为了防止越界。
这题只有单点，所以每次将所求结点旋自根节点即可。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 200010
#define LL __int64
#define INF 0xfffffff
#define key_value ch[ch[root][1]][0]
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
int pre[N],s[N],size[N];
int ch[N][],a[N],val[N];
int root,n,tot;
void newnode(int &x,int k,int fa)
{
x = ++tot;
ch[x][]=ch[x][] = ;
pre[x] = fa;
size[x] = ;
s[x] = k;
val[x] = k;
}
void pushup(int w)
{
size[w] = size[ch[w][]]+size[ch[w][]]+;
s[w] = max(max(s[ch[w][]],s[ch[w][]]),val[w]);
// cout<<s[w]<<" "<<w<<"// "<<" "<<ch[w][1]<<" "<<s[w]<<endl;
}
void rotate(int r,int kind)
{
int y = pre[r];
ch[y][!kind] = ch[r][kind];
pre[ch[r][kind]] = y;
if(pre[y])
{
ch[pre[y]][ch[pre[y]][]==y] = r;
}
pre[r] = pre[y];
ch[r][kind] = y;
pre[y] = r;
pushup(y);
//pushup(r);
}
void splay(int r,int goal)
{
while(pre[r]!=goal)
{
if(pre[pre[r]]==goal)
{
rotate(r,ch[pre[r]][]==r);
}
else
{
int y = pre[r];
int kind = (ch[pre[y]][]==y);
if(ch[y][kind]==r)
{
rotate(r,!kind);
rotate(r,kind);
}
else
{
rotate(y,kind);
rotate(r,kind);
}
}
}
pushup(r);
if(goal==) root = r;
}
int get_k(int k)
{
int r = root;
while(size[ch[r][]]!=k)
{
if(size[ch[r][]]>k)
r = ch[r][];
else
{
k-=(size[ch[r][]]+);
r = ch[r][];
}
}
return r;
}
int query(int l,int r)
{
splay(get_k(l-),);
splay(get_k(r+),root);
return s[key_value];
}
/*void update(int l,int r,int k)
{
splay(get_k(l-1),0);
splay(get_k(r+1),root);
val[key_value] = k;
s[key_value] = k;
pushup(ch[root][1]);
pushup(root);
}*/
void update(int l,int r,int k)
{
int kk = get_k(l);
val[kk] = k;
splay(kk,);
}
void build(int &w,int l,int r,int fa)
{
if(l>r) return ;
int m = (l+r)>>;
newnode(w,a[m],fa);
build(ch[w][],l,m-,w);
build(ch[w][],m+,r,w);
pushup(w);
}
void init()
{
int i;
for(i = ;i < n ;i++)
scanf("%d",&a[i]);
ch[][] = ch[][] = pre[] = size[] = s[] = ;
root = tot =;
newnode(root,-,);
newnode(ch[root][],-,root);
size[root] = ;
build(key_value,,n-,ch[root][]);
pushup(ch[root][]);
pushup(root);
}
int main()
{
int q,x,y,i;
char sq[];
while(scanf("%d%d",&n,&q)!=EOF)
{
init();
while(q--)
{
scanf("%s%d%d",sq,&x,&y);
if(sq[]=='U')
{
update(x,x,y);
/*for(i = 0; i <= n+2; i++)
cout<<ch[i][0]<<" "<<ch[i][1]<<" "<<i<<endl;
puts("");*/
}
else
{
printf("%d\n",query(x,y));
/*for(i = 0; i <= n+2; i++)
cout<<ch[i][0]<<" "<<ch[i][1]<<" "<<i<<endl;
puts("");*/
}
}
}
return ;
}