HDU_1754
这个算是我的splay的处女作了，要不是为了练splay真心不想把这个可以用线段树轻松搞定的题敲得这么复杂……努力了一下午+半个晚上终于把splay的基本操作搞懂了。
其实感觉splay的旋转操作和SBT差不多，只不过多了人字旋转和一字旋转，这样要比单一从底向上旋转更能维护splay的树高。
另外对于一个问题说一点自己的看法：splay要写一个rotate_to的函数，就是将某个位置的元素旋转到goal的下方，而为什么是下方而不是恰好旋转到goal呢？因为如果是设定恰好旋转到goal的话，最后一步会把goal旋转跑，就没办法判定是否旋转到位了，所以要写成旋转到goal的下方，这样goal就是固定不动的了。也正是因为这样，根结点T的父节点pre[T]要置为0，这样就能保证splay上的任意一个位置都有其“上方”的一个位置作为goal。
#include<stdio.h>
#include<string.h>
#define MAXD 200010
#define INF 0x3f3f3f3f
int N, M, T, node, left[MAXD], right[MAXD], size[MAXD], key[MAXD], max[MAXD], pre[MAXD], a[MAXD];
int getmax(int x, int y, int z)
{
int t = x > y ? x : y;
return t > z ? t : z;
}
void update(int x)
{
size[x] = size[left[x]] + size[right[x]] + 1;
max[x] = getmax(key[x], max[left[x]], max[right[x]]);
}
void left_rotate(int x)
{
int y = right[x], p = pre[x];
right[x] = left[y];
if(right[x])
pre[right[x]] = x;
left[y] = x;
pre[x] = y;
pre[y] = p;
if(p != 0)
right[p] == x ? right[p] = y : left[p] = y;
else
T = y;
update(x);
}
void right_rotate(int x)
{
int y = left[x], p = pre[x];
left[x] = right[y];
if(left[x])
pre[left[x]] = x;
right[y] = x;
pre[x] = y;
pre[y] = p;
if(p != 0)
right[p] == x ? right[p] = y : left[p] = y;
else
T = y;
update(x);
}
void add(int &T, int v)
{
T = ++ node;
key[T] = max[T] = v;
size[T] = 1;
left[T] = right[T] = 0;
}
void build(int &T, int x, int y, int fa)
{
int mid = (x + y) / 2;
add(T, a[mid]);
pre[T] = fa;
if(x < mid)
build(left[T], x, mid - 1, T);
if(mid < y)
build(right[T], mid + 1, y, T);
update(T);
}
void init()
{
int i, j, k;
T = node = left[0] = right[0] = size[0] = 0;
max[0] = key[0] = -INF;
add(T, -INF), add(right[T], -INF);
pre[T] = 0, pre[node] = T;
size[T] = 2;
for(i = 1; i <= N; i ++)
scanf("%d", &a[i]);
build(left[right[T]], 1, N, right[T]);
update(right[T]), update(T);
}
void splay(int x, int goal)
{
int y, z;
for(;;)
{
if((y = pre[x]) == goal)
break;
if((z = pre[y]) == goal)
right[y] == x ? left_rotate(y) : right_rotate(y);
else
{
if(right[z] == y)
{
if(right[y] == x)
left_rotate(z), left_rotate(y);
else
right_rotate(y), left_rotate(z);
}
else
{
if(left[y] == x)
right_rotate(z), right_rotate(y);
else
left_rotate(y), right_rotate(z);
}
}
}
update(x);
}
void rotate_to(int k, int goal)
{
int i = T, n;
for(;;)
{
n = size[left[i]] + 1;
if(n == k)
break;
if(k < n)
i = left[i];
else
{
k -= n;
i = right[i];
}
}
splay(i, goal);
}
void query(int x, int y)
{
rotate_to(x, 0), rotate_to(y + 2, T);
printf("%d\n", max[left[right[T]]]);
}
void refresh(int x, int v)
{
rotate_to(x + 1, 0);
key[T] = v;
update(T);
}
void solve()
{
int i, j, k, x, y;
char b[5];
for(i = 0; i < M; i ++)
{
scanf("%s%d%d", b, &x, &y);
if(b[0] == 'Q')
query(x, y);
else
refresh(x, y);
}
}
int main()
{
while(scanf("%d%d", &N, &M) == 2)
{
init();
solve();
}
return 0;
}