题意就是简单的点更新，成段查询。
splay tree 果真是常数比较大的log(n)操作。 比线段树还慢了这么多。
//
// main.cpp
// splay
//
// Created by 陈加寿 on 16/3/25.
// Copyright © 2016年 chenhuan001. All rights reserved.
// #include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; //来一发点更新，成段查询
#define MAXN 1001000
#define INF 1001000000 struct Splay_Tree
{
int cnt, rt;
struct node
{
int K,mxk;
int key, size, fa, son[];
void set(int _key, int _size, int _fa,int _K)
{
mxk = K = _K;//这个表示这个节点的值
key = _key;//这个为ID
size=_size;
fa=_fa;
son[]=son[]=;
}
}T[MAXN];
inline void init()
{
cnt=;
T[cnt++].set(, , , );//
rt = ;
//初始化的时候，把0这个节点的K设置为INF
}
inline void PushUp(int x)
{
//这一步就很关键了
T[x].size=T[T[x].son[]].size+T[T[x].son[]].size+;
T[x].mxk = max(T[x].K,max(T[T[x].son[]].mxk,T[T[x].son[]].mxk));
} inline void Rotate(int x, int p) //0左旋 1右旋
{
int y=T[x].fa;
T[y].son[!p]=T[x].son[p];
T[T[x].son[p]].fa=y;
T[x].fa=T[y].fa;
if(T[x].fa)
T[T[x].fa].son[T[T[x].fa].son[] == y]=x;
T[x].son[p]=y;
T[y].fa=x;
PushUp(y);//先更新y
PushUp(x);//再更新x
} void Splay(int x, int To) //将x节点插入到To的子节点中
{
while(T[x].fa != To)
{
if(T[T[x].fa].fa == To)
Rotate(x, T[T[x].fa].son[] == x);
else
{
int y=T[x].fa, z=T[y].fa;
int p=(T[z].son[] == y);
if(T[y].son[p] == x)
Rotate(x, !p), Rotate(x, p); //之字旋
else
Rotate(y, p), Rotate(x, p); //一字旋
}
}
if(To == ) rt=x;
} int find(int key) //返回值为key的节点 若无返回0 若有将其转移到根处
{
int x=rt;
while(x && T[x].key != key)
x=T[x].son[key > T[x].key];
if(x) Splay(x, );
return x;
} int prev() //返回比根值小的最大值 若无返回0 若有将其转移到根处
{
int x=T[rt].son[];
if(!x) return ;
while(T[x].son[])
x=T[x].son[];
Splay(x, );
return x;
} int next() //返回比根值大的最小值 若无返回0 若有将其转移到根处
{
int x=T[rt].son[];
if(!x) return ;
while(T[x].son[])
x=T[x].son[];
Splay(x, );
return x;
} void Insert(int key,int K) //插入key 并且将该节点转移到根处
{
if(!rt)
T[rt = cnt++].set(key, , , K);
else
{
int x=rt, y=;
while(x)
{
y=x;
x=T[x].son[key > T[x].key];
}
T[x = cnt++].set(key, , y, K);
T[y].son[key > T[y].key]=x;
Splay(x, );
}
} void Delete(int key) //删除值为key的节点 若有重点只删其中一个 x的前驱移动到根处
{
int x=find(key);
if(!x) return;
int y=T[x].son[];
while(T[y].son[])
y=T[y].son[];
int z=T[x].son[];
while(T[z].son[])
z=T[z].son[];
if(!y && !z)
{
rt=;
return;
}
if(!y)
{
Splay(z, );
T[z].son[]=;
PushUp(z);
return;
}
if(!z)
{
Splay(y, );
T[y].son[]=;
PushUp(y);
return;
}
Splay(y, );
Splay(z, y);
T[z].son[]=;
PushUp(z);
PushUp(y);
} int GetPth(int p) //获得第p小的节点 并将其转移到根处
{
if(!rt) return ;
int x=rt;
while(x)
{
if(p == T[T[x].son[]].size+)
break;
if(p>T[T[x].son[]].size+)
{
p-=T[T[x].son[]].size+;
x=T[x].son[];
}
else
x=T[x].son[];
}
Splay(x, );
return x;
} int GetRank(int key) //获得值<=key的节点个数 并将其转移到根处 若<key只需将<=换为<
{
if(!rt) return ;
int x=rt, ret=, y=;
while(x)
{
y=x;
if(T[x].key <= key)
{
ret+=T[T[x].son[]].size+;
x=T[x].son[];
}
else
x=T[x].son[];
}
Splay(y, );
return ret;
}
}spt; int main() {
//两种操作
//一、修改某个节点值
//二、区间查询
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
spt.init();
for(int i=;i<=n;i++)
{
int tmp;
scanf("%d",&tmp);
spt.Insert(i, tmp);
}
char sign;
for(int i=;i<m;i++)
{
getchar();
int a,b;
scanf("%c %d %d",&sign,&a,&b);
if(sign == 'Q')
{
if(a == b)
{
int id = spt.GetPth(a);
printf("%d\n",spt.T[id].K);//区间只有一个点的时候
continue;
}
int idb = spt.GetPth(b);
int ida = spt.GetPth(a);
spt.Splay(idb, ida);
int idson = spt.T[idb].son[];
int mx = max( spt.T[idson].mxk ,max(spt.T[ida].K,spt.T[idb].K));
printf("%d\n",mx);
}
else
{
//更新操作
int id = spt.GetPth(a);
spt.T[id].K = b;
spt.PushUp(id);
}
}
}
return ;
}