BZOJ 1552 「CERC2007」Robotic Sort

没有权限号的同学可以到 BZOJ 3506 交一下……

同 OJ 1552

不管怎么翻转，如果我们只交换左右儿子的索引而不是信息，第 K 大的结点永远都是不变的。
所以我们可以先排一次序，并在按原序列插入时记录每个第 K 大的结点。
那么问题就转到如何求一个结点的名次。

我们从根结点到这个结点把翻转标记全部下传，然后依次加入左子树的结点数 + 1 并逐步跳到根结点。
然后区间翻转就是 FHQ Treap 一个简单的操作了……

代码：

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define ls(p) tree[p].lson
#define rs(p) tree[p].rson
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    while(ch < '0' || ch > '9')
        w |= ch == '-',ch = gc();
    while(ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
    w ? x = -x : x;
}

const int N = 1e5;
int n,a[N + 10],rk[N + 10],kth[N + 10];
struct rec
{
    int id,val;
    inline bool operator<(const rec &a) const
    {
        return val < a.val || (val == a.val && id < a.id);
    }
} b[N + 10];
struct node
{
    int val,rnd,sz;
    int rev;
    int lson,rson,fa;
} tree[N + 10];
inline int new_node(int v)
{
    static int tot = 0;
    tree[++tot].val = v;
    tree[tot].rnd = rand();
    tree[tot].sz = 1;
    return tot;
}
inline void up(int p)
{
    tree[p].sz = tree[ls(p)].sz + 1 + tree[rs(p)].sz;
    if(ls(p))
        tree[ls(p)].fa = p;
    if(rs(p))
        tree[rs(p)].fa = p;
}
inline void down(int p)
{
    if(tree[p].rev)
    {
        swap(ls(p),rs(p));
        if(ls(p))
            tree[ls(p)].rev ^= 1;
        if(rs(p))
            tree[rs(p)].rev ^= 1;
        tree[p].rev = 0;
    }
}
inline void down_from_top(int p)
{
    if(tree[p].fa)
        down_from_top(tree[p].fa);
    down(p);
}
void split(int p,int k,int &x,int &y)
{
    if(!p)
    {
        x = y = 0;
        return ;
    }
    down(p);
    if(tree[ls(p)].sz < k)
        x = p,split(rs(p),k - tree[ls(p)].sz - 1,rs(p),y);
    else
        y = p,split(ls(p),k,x,ls(p));
    up(p);
}
int merge(int x,int y)
{
    if(!x || !y)
        return x | y;
    down(x),down(y);
    if(tree[x].rnd < tree[y].rnd)
    {
        rs(x) = merge(rs(x),y);
        up(x);
        return x;
    }
    else
    {
        ls(y) = merge(x,ls(y));
        up(y);
        return y;
    }
}
int get_rank(int p)
{
    down_from_top(p);
    int ret = tree[ls(p)].sz + 1;
    while(tree[p].fa)
    {
        if(rs(tree[p].fa) == p)
            ret += tree[ls(tree[p].fa)].sz + 1;
        p = tree[p].fa;
    }
    return ret;
}
int p,x,y,z,t;
int main()
{
    read(n);
    for(register int i = 1;i <= n;++i)
        read(a[i]),b[i] = (rec){i,a[i]};
    sort(b + 1,b + n + 1);
    for(register int i = 1;i <= n;++i)
        rk[b[i].id] = i;
    for(register int i = 1;i <= n;++i)
        p = merge(p,kth[rk[i]] = new_node(a[i]));
    for(register int i = 1;i <= n;++i)
    {
        t = get_rank(kth[i]);
        printf("%d ",t);
        split(p,t,x,z);
        split(x,i - 1,x,y);
        tree[y].rev ^= 1;
        p = merge(merge(x,y),z);
    }
}