HDU_1890
第一次写涉及到区间翻转的splay，结果就没注意到翻转的操作类似于线段树中对区间0、1取反的操作，下传标记的时候记录翻转的标记rev应该是加1模2，而不能简单地将左右儿子的rev置为1。
下面说说具体的思路吧。
我们每次可以先将“最小”的点旋转到根，那么根左边的区间自然就是要翻转的区间了，于是我们对根左边的区间打上翻转的标记，然后将根删除，如此反复N-1遍。对于每次要输出的值，假设我们现在试图令第i个block到位，那么把这个点旋转到根后，输出i+size[left[T]]即可，其中T表示根。当然，最后还要输出一个N。
然而，我们要如何知道每次该旋转哪个block呢？即便我们知道该旋转哪个block，那这个block在splay中又处于哪个位置呢？对于第一个问题，我们可以先将block排个序，这样自然就知道每次该旋转哪个block了。对于第二个问题，我们可以在建树的过程中把每个block所在的节点的标号存下来即可。这样我们每次就可以很方便的知道该旋转哪个block了，同时也能方便地知道它在splay中的位置，但是这时我们不能直接调用splay操作把这个点旋转上去，因为这个节点的上方有可能还有一些翻转的标记没有下传，因此我们要先从这个节点开始向上找到根，并在找的过程中记录一下路径，然后再从根节点向下沿记录好的路径去找要旋转的节点，并在找的过程中下传翻转标记。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 100010
int N, node, T, height[MAXD], size[MAXD], pre[MAXD], left[MAXD], right[MAXD], rev[MAXD], P[MAXD];
struct Block
{
int key, cur;
}block[MAXD];
int cmp(const void *_p, const void *_q)
{
Block *p = (Block *)_p, *q = (Block *)_q;
if(height[p->key] == height[q->key])
return p->key - q->key;
return height[p->key] < height[q->key] ? -1 : 1;
}
void newnode(int &cur, int k)
{
cur = ++ node;
block[k].key = k, block[k].cur = cur;
left[cur] = right[cur] = 0;
rev[cur] = 0;
}
void update(int cur)
{
size[cur] = size[left[cur]] + size[right[cur]] + 1;
}
void pushdown(int cur)
{
if(rev[cur])
{
int ls = left[cur], rs = right[cur];
rev[ls] = (rev[ls] + 1) % 2, rev[rs] = (rev[rs] + 1) % 2;
left[cur] = rs, right[cur] = ls;
rev[cur] = 0;
}
}
void build(int &cur, int x, int y, int p)
{
int mid = (x + y) / 2;
newnode(cur, mid);
size[cur] = y - x + 1;
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);
}
void init()
{
int i;
T = node = left[0] = right[0] = size[0] = 0;
for(i = 1; i <= N; i ++)
scanf("%d", &height[i]);
build(T, 1, N, 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);
}
void rotateto(int x)
{
int i;
for(i = x; i != T; i = pre[i])
P[pre[i]] = i;
for(i = T;;)
{
pushdown(i);
if(i == x)
break;
i = right[i] == P[i] ? right[i] : left[i];
}
splay(x, 0);
}
int Delete(int &x)
{
int k;
pushdown(x);
-- size[x];
if(x == T || right[x] == 0)
{
if(right[x] == 0)
{
k = x;
if(left[x])
pre[left[x]] = pre[x];
x = left[x];
}
else
{
k = Delete(left[x]);
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);
}
return k;
}
else
return Delete(right[x]);
}
void Remove()
{
int i, p;
rev[left[T]] = (rev[left[T]] + 1) % 2;
if(left[T] == 0 || right[T] == 0)
{
T = left[T] + right[T];
pre[T] = 0;
}
else
Delete(T);
}
void solve()
{
int i;
qsort(block + 1, N, sizeof(block[0]), cmp);
for(i = 1; i < N; i ++)
{
rotateto(block[i].cur);
printf("%d ", i + size[left[T]]);
Remove();
}
printf("%d\n", N);
}
int main()
{
for(;;)
{
scanf("%d", &N);
if(!N)
break;
init();
solve();
}
return 0;
}