HDU_3436
这个题目无论用什么方法做，首先离散化时候一定要处理好，否则后面会越想越乱。一个比较好的离散化的思路就是把需要Top和Query点看成一个小区间，然后把这些点之间的部分，以及头尾两个部分看成其他的一个一个的区间。
线段树或者树状数组的做法可以参考http://www.cppblog.com/Yuan/archive/2010/08/18/123871.html，我就只说一下用splay的思路吧。
维护splay只需要维护一个size，但这个size表示的不是子树的节点数，而是子树上的所有区间所包含的点的总数。
对于top操作，由于我们要先找到那个点（或者说是小区间）的节点标号（每个区间对应的splay上的节点标号可以在建树的时候处理出来，查找节点标号的时候由于离散化后区间是有序存储的，所以可以对存区间的数组二分查找来找到这个小区间），然后将这个点旋转根后删除，再重新插入这个点。
对于Query操作，我们只需要把这个点旋转到根，然后输出size[left[T]]+1即可。
对于Rank操作，我们可以从上到下查找，直到确定某个区间包含这个位置时再将其计算出来即可。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 100010
int N, Q, T, node, tx[MAXD], begin[MAXD], end[MAXD], nodep[MAXD];
int num[2 * MAXD], size[2 * MAXD], left[2 * MAXD], right[2 * MAXD], pre[2 * MAXD], key[2 * MAXD];
char b[MAXD][10];
int ob[MAXD];
int cmp(const void *_p, const void *_q)
{
int *p = (int *)_p, *q = (int *)_q;
return *p - *q;
}
void update(int cur)
{
size[cur] = size[left[cur]] + size[right[cur]] + num[cur];
}
void newnode(int &cur, int k)
{
cur = ++ node;
size[cur] = num[cur] = end[k] - begin[k] + 1;
key[cur] = k;
nodep[k] = cur;
left[cur] = right[cur] = 0;
}
void build(int &cur, int x, int y, int p)
{
int mid = (x + y) / 2;
newnode(cur, mid);
pre[cur] = p;
if(x == y)
return ;
if(x < mid)
build(left[cur], x, mid - 1, cur);
if(mid < y)
build(right[cur], mid + 1, y, cur);
update(cur);
}
void init()
{
int i, j, k;
scanf("%d%d", &N, &Q);
k = 0;
tx[k ++] = 0;
for(i = 0; i < Q; i ++)
{
scanf("%s%d", b[i], &ob[i]);
if(b[i][0] == 'T' || b[i][0] == 'Q')
tx[k ++] = ob[i];
}
tx[k ++] = N;
qsort(tx, k, sizeof(tx[0]), cmp);
N = 0;
for(i = 1; i < k; i ++)
if(tx[i] != tx[i - 1])
{
if(tx[i] - tx[i - 1] > 1)
{
begin[N] = tx[i - 1] + 1, end[N] = tx[i] - 1;
++ N;
}
begin[N] = end[N] = tx[i];
++ N;
}
T = node = left[0] = right[0] = size[0] = num[0] = 0;
build(T, 0, N - 1, 0);
}
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);
}
int BS(int x)
{
int max, mid, min;
min = 0, max = N;
for(;;)
{
mid = (max + min) / 2;
if(mid == min)
break;
if(begin[mid] <= x)
min = mid;
else
max = mid;
}
return mid;
}
int Delete(int &cur, int p)
{
int k;
if(cur == T || right[cur] == 0)
{
if(cur == T)
{
k = Delete(left[cur], cur);
left[k] = left[T], right[k] = right[T];
if(left[k])
pre[left[k]] = k;
if(right[k])
pre[right[k]] = k;
T = k;
pre[T] = 0;
update(T);
}
else
{
k = cur;
if(left[k])
pre[left[k]] = p;
cur = left[k];
}
return k;
}
else
{
k = Delete(right[cur], cur);
update(cur);
return k;
}
}
void Insert(int &cur, int k, int p)
{
if(cur == 0)
{
newnode(cur, k);
pre[cur] = p;
return ;
}
Insert(left[cur], k, cur);
update(cur);
}
void Top(int x)
{
int k, cur;
k = BS(x);
cur = nodep[k];
splay(cur, 0);
if(left[T] == 0 || right[T] == 0)
{
T = left[T] + right[T];
pre[T] = 0;
}
else
Delete(T, 0);
Insert(T, k, 0);
splay(node, 0);
}
void Query(int x)
{
int k, cur;
k = BS(x);
cur = nodep[k];
splay(cur, 0);
printf("%d\n", size[left[cur]] + 1);
}
int Search(int cur, int x)
{
int ls = left[cur], rs = right[cur], k = key[cur];
if(x <= size[ls])
return Search(left[cur], x);
else if(x <= size[ls] + num[cur])
return begin[k] + (x - size[ls]) - 1;
else
return Search(right[cur], x - size[ls] - num[cur]);
}
void Rank(int x)
{
printf("%d\n", Search(T, x));
}
void solve()
{
int i, j, k;
for(i = 0; i < Q; i ++)
{
if(b[i][0] == 'T')
Top(ob[i]);
else if(b[i][0] == 'Q')
Query(ob[i]);
else
Rank(ob[i]);
}
}
int main()
{
int t, tt;
scanf("%d", &t);
for(tt = 0; tt < t; tt ++)
{
init();
printf("Case %d:\n", tt + 1);
solve();
}
return 0;
}