题意：与区间查询点更新，点有20W个，询问区间的最大值。曾经用线段树，1000+ms,今天的伸展树，890没ms，差不多。
第一次学习伸展树，一共花了2个单位时间，感觉伸展树真很有用，也很好玩。现在只学了一点点。切个点更新试试。
大致思路：用编号（数组）作为树的键值建树，每插一个数，沿路节点更新最大值（每个结点有一个附加信息标记以之为子树的树所有点的最大值）。所以，查询时【i,j】，只要把i-1伸展到树根，把j+1伸展到I-1下面，那么j+1的左子树就是要的区间了！查该子树根值信息即可（特判端点）！同理，更新操作，只要把待更新的伸展到根，然后更新它，同时维护一下信息即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int maxx=200010;
int a[maxx];int child[maxx][2];int fa[maxx];int maxo[maxx]; //a[i]是原来数组值，child左右孩子（0,1）,maxo【i】是以序号i为根的子树（包括自身）的最大值。
int root=0;
void inline maintain(int n) //点被修改后，该点值的维护
{
maxo[n]=maxo[n]>a[n]?maxo[n]:a[n];
}
void inline rotate(int x,int f) //f=1右旋，f=0左旋
{
int y=fa[x];
maxo[x]=maxo[y]; //最大值的更新
maxo[y]=maxo[child[x][f]]>maxo[child[y][f]]?maxo[child[x][f]]:maxo[child[y][f]];
maintain(y);
child[y][!f]=child[x][f]; //三次的重连线，注意顺序。
fa[child[x][f]]=y;
if(fa[y])
{
if(y==child[fa[y]][0])
child[fa[y]][0]=x;
else
child[fa[y]][1]=x;
}
else
{
root=x;
}
fa[x]=fa[y];
child[x][f]=y;
fa[y]=x;
}
void splay(int n,int goal) //把序号为i的点转到点goal下面的孩子。
{
while(fa[n]!=goal) //一直左右旋即可
{
int y=fa[n];
rotate(n,child[y][0]==n?1:0);
}
}
void inline insert(int n) //插入来建树
{
int temp=root;
if(root==0) //根节点
{
root=n;
maxo[n]=n;
return ;
}
else
{
while(1)
{
maxo[temp]=maxo[temp]<a[n]?a[n]:maxo[temp];//插入时候维护最大值
if(n<temp) //左边
{
if(child[temp][0]==0)
{
child[temp][0]=n;
fa[n]=temp;
maxo[n]=a[n];
splay(n,0); //注意这里要伸展，否则建树就是一般的排序二叉树，会超时
return ;
}
temp=child[temp][0];
}
else //右边
{
if(child[temp][1]==0)
{
child[temp][1]=n;
fa[n]=temp;
maxo[n]=a[n];
splay(n,0);
return ;
}
temp=child[temp][1];
}
}
}
}
void update(int n,int x) //更新 ，把序号为n的值更新为x
{
splay(n,0);
a[n]=x;
maxo[n]=maxo[child[n][0]]>maxo[child[n][1]]?maxo[child[n][0]]:maxo[child[n][1]];
maintain(n);
}
void clear() //初始化
{
root=0;
for(int i=0;i<maxx;i++)
{
maxo[i]=child[i][0]=child[i][1]=fa[i]=0;
}
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
clear();
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
insert(i);
}
char q;int i,j;
while(m--)
{
getchar();
scanf("%c%d%d",&q,&i,&j);
if(q=='Q')
{
int ans=0;
if(i==1&&j!=n) //区间端点的特判
{
splay(j+1,0);
ans=maxo[child[j+1][0]];
}
else if(i!=1&&j==n)
{
splay(i-1,0);
ans=maxo[child[i-1][1]];
}
else if(i==1&&j==n)
{
ans=maxo[root];
}
else
{
splay(i-1,0);
splay(j+1,i-1);
ans=maxo[child[j+1][0]];
}
printf("%d
",ans);
}
else
{
update(i,j);
}
}
}
return 0;
}