Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 这让很多学生很反感。
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
本题目包含多组测试，请处理到文件结束。 在每个测试的第一行，有两个正整数 N 和 M (
0<N≤200000
，
0<M<5000
)，分别代表学生的数目和操作的数目。 学生ID编号分别从1编到N。 第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。 接下来有M行。每一行有一个字符 C (只取’Q’或’U’) ，和两个正整数A，B。 当C为’Q’的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。 当C为’U’的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
Output
对于每一次询问操作，在一行里面输出最高成绩。
5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5
Sample Output
5 6 5 9
Hint
Huge input,the C function scanf() will work better than cin
Solution
这题一看就是简单的线段树（单点修改+区间求最值）
但这次我用的是 Splay 来维护，目的是练一练模板。
有要注意的是：下标要从2到n+1，这样好处理。代码如下：
Code
#include<cstdio>
#include<cstring>
#define clr(a) memset(a,0,sizeof(a))
using namespace std;
const int N=
200003;
int n,m,tot,root;
int s[N][
2],fa[N],key[N],mx[N],size[N];
int a[N];
char ch[
2];
inline int read()
{
int data=
0;
char ch=
0;
while(ch<
'0' || ch>
'9') ch=getchar();
while(ch>=
'0' && ch<=
'9') data=data*
10+ch-
'0',ch=getchar();
return data;
}
inline int max(
int x,
int y)
{
return x>y?x:y;
}
inline bool pd(
int x)
{
return x==s[fa[x]][
1];
}
inline void update(
int x)
{
mx[x]=max(key[x],max(mx[s[x][
0]],mx[s[x][
1]]));
size[x]=size[s[x][
0]]+size[s[x][
1]]+
1;
}
inline void rotate(
int x)
{
int y=fa[x],w=pd(x);
fa[s[y][w]=s[x][w^
1]]=y;
update(y);
if(fa[x]=fa[y]) s[fa[y]][pd(y)]=x;
s[fa[y]=x][w^
1]=y;
}
inline void splay(
int x,
int num)
{
for(
int y;(y=fa[x])!=num;rotate(x))
if(fa[y]!=num) rotate(pd(x)==pd(y)?y:x);
update(x);
if(!num) root=x;
}
inline void make(
int l,
int r,
int &rt,
int x)
{
if(l>r)
return;
int mid=(l+r)>>
1;
rt=++tot;
key[rt]=a[mid];
fa[rt]=x;
make(l,mid-
1,s[rt][
0],rt);
make(mid+
1,r,s[rt][
1],rt);
update(rt);
}
inline void get(
int x,
int num)
{
int k=root;
while(x!=size[s[k][
0]]+
1)
if(x<size[s[k][
0]]+
1) k=s[k][
0];
else
{
x-=size[s[k][
0]]+
1;
k=s[k][
1];
}
splay(k,num);
}
inline void change(
int x,
int y)
{
get(x,
0);
key[root]=y;
update(root);
}
inline int query(
int x,
int y)
{
get(x-
1,
0);
get(y+
1,root);
return mx[s[s[root][
1]][
0]];
}
int main()
{
while(~
scanf(
"%d%d",&n,&m))
{
clr(mx),clr(s);
root=tot=
0;
a[
1]=a[n+
2]=-
1;
for(
int i=
2;i<=n+
1;i++) a[i]=read();
make(
1,n+
2,root,
0);
while(m--)
{
scanf(
"%s",&ch);
int x=read(),y=read();
if(ch[
0]==
'U') change(x+
1,y);
else
printf(
"%d\n",query(x+
1,y+
1));
}
}
return 0;
}
