POJ_2892
这个题目用splay去想还是比较直接的，但之所以感觉思路比较直接，也是因为前面又巩固、学习了一下线段树的一些对于区间合并的操作，更多的涉及线段树区间合并的题目可以参考胡浩的博客http://www.notonlysuccess.com/index.php/segment-tree-complete/。
当然，这个题目是可以用线段树去做的，而且和splay去做是比较相似的，查询的时候都是去找这个点左半部分区间的右边有多少个连续的1，以及这个点右半部分区间的左边有多少个连续的1。
下面还是说一下我用splay做的时候的一些思路吧。
首先要明确的就是splay上一个节点表示的是一个区间，而区间的范围就是以这个节点为根的整棵子树。我们可以用lc[](left contiguous)表示一个区间从左边开始连续有多少个1（1表是点没有被破坏），rc[](right contiguous)表示一个区间从右边开始连续有多少个1，flag[]表示当前的点是否被破坏。
如果要查询一个点左右一共有多少个连续1，那么就只需要把这个点旋转到根，然后看这个点是否被破坏，如果没有破坏就输出rc[left[T]]+lc[right[T]]+1，否则就输出0。如果要破坏一个点，就把这个点旋转到根，然后把flag[T]变为0后，并更新一个这个节点记录的信息即可。修复一个点和破坏一个点是类似的。
#include<stdio.h>
#include<string.h>
#define MAXD 50010
int N, M, T, node, size[MAXD], d[MAXD], cnt;
int key[MAXD], flag[MAXD], pre[MAXD], left[MAXD], right[MAXD], lc[MAXD], rc[MAXD];
void newnode(int &cur, int k)
{
cur = ++ node;
key[cur] = k;
flag[cur] = 1;
size[cur] = 1;
left[cur] = right[cur] = 0;
}
void update(int cur)
{
int ls = left[cur], rs = right[cur];
size[cur] = size[ls] + size[rs] + 1;
lc[cur] = lc[ls], rc[cur] = rc[rs];
if(flag[cur] != 0)
{
if(rc[rs] == size[rs])
rc[cur] += rc[ls] + 1;
if(lc[ls] == size[ls])
lc[cur] += lc[rs] + 1;
}
}
void build(int &cur, int x, int y, int p)
{
int mid = (x + y) / 2;
newnode(cur, mid);
pre[cur] = p;
if(x == y)
{
lc[cur] = rc[cur] = 1;
return ;
}
if(x < mid)
build(left[cur], x, mid - 1, cur);
if(mid < y)
build(right[cur], mid + 1, y, cur);
update(cur);
}
void leftrotate(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)
T = y;
else
right[p] == x ? right[p] = y : left[p] = y;
update(x);
}
void rightrotate(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)
T = y;
else
right[p] == x ? right[p] = y : left[p] = y;
update(x);
}
void splay(int x, int goal)
{
int y, z;
for(;;)
{
if((y = pre[x]) == goal)
break;
if((z = pre[y]) == goal)
right[y] == x ? leftrotate(y) : rightrotate(y);
else
{
if(right[z] == y)
{
if(right[y] == x)
leftrotate(z), leftrotate(y);
else
rightrotate(y), leftrotate(z);
}
else
{
if(left[y] == x)
rightrotate(z), rightrotate(y);
else
leftrotate(y), rightrotate(z);
}
}
}
update(x);
}
void rotateto(int v, int goal)
{
int i;
for(i = T;;)
{
if(v == key[i])
break;
if(v < key[i])
i = left[i];
else
i = right[i];
}
splay(i, goal);
}
void init()
{
T = node = left[0] = right[0] = size[0] = lc[0] = rc[0] = 0;
build(T, 1, N, 0);
}
void destroy(int v)
{
rotateto(v, 0);
flag[T] = 0;
update(T);
}
void repair(int v)
{
rotateto(v, 0);
flag[T] = 1;
update(T);
}
void query(int v)
{
rotateto(v, 0);
if(flag[T] == 0)
printf("0\n");
else
printf("%d\n", rc[left[T]] + lc[right[T]] + 1);
}
void solve()
{
int i, j, k;
char b[5];
cnt = 0;
for(i = 0; i < M; i ++)
{
scanf("%s", b);
if(b[0] == 'D')
{
scanf("%d", &k);
d[cnt ++] = k;
destroy(k);
}
else if(b[0] == 'R')
{
-- cnt;
repair(d[cnt]);
}
else
{
scanf("%d", &k);
query(k);
}
}
}
int main()
{
while(scanf("%d%d", &N, &M) == 2)
{
init();
solve();
}
return 0;
}