HDU 1890 splay

题

HDU

解

题意：每次输出pos[i]后翻转[i,pos[i]]。

裸splay。
如何获得当前i的位置困扰了好久。
网上都是使用另一种魔性splay写法，直接把某一指针提到根……然而我是lrj写法无力啊……
@plm大神表示记录每个点代表的指针即可。事实上还要记录父指针。
寻找i的位置的过程最后我研究出这种写法：如果它是父亲的右孩子，那么计数加上左孩子size+1（父节点本身）；左孩子则不管；若有翻转标记则不动标记直接ret = size(o) + 1 - ret;把计数“反”过来。注意特判初始节点。

码（11784K, 436ms）

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}

const int maxn = 1e5 + 100;

struct Node
{
    int v;
    bool rev;
    int size;
    Node *fa;
    Node *ch[2];
    Node(int a = 0, Node *b = NULL) : v(a), rev(false), size(1), fa(b) {ch[0] = ch[1] = NULL;}
} *root;

#define lc(o) (o -> ch[0])
#define rc(o) (o -> ch[1])
#define v(o) (o -> v)
#define fa(o) (o -> fa)
#define rev(o) (o -> rev)
#define size(o) (o ? o -> size : 0)

inline int cmp(Node *o, int k) {return size(lc(o)) == k - 1 ? -1 : (size(lc(o)) < k ? 1 : 0);}
inline void pushdown(Node* &o) {if(!o||!rev(o))return;if(lc(o))rev(lc(o)) ^= 1; if(rc(o))rev(rc(o)) ^= 1; swap(lc(o), rc(o)); rev(o) = false;}
inline void maintain(Node* &o) {if(!o)return; o -> size = size(lc(o)) + size(rc(o)) + 1;}

inline void rotate(Node* &o, int d)
{
    pushdown(o); 
    Node *p = o -> ch[d ^ 1];
    pushdown(p);
    o -> ch[d ^ 1] = p -> ch[d];    if(p -> ch[d])fa(p -> ch[d]) = o; fa(p) = fa(o);
    p -> ch[d] = o;                    fa(o) = p;
    maintain(o); maintain(p);
    o = p;    
}

void splay(Node* &o, int k)
{
    if(!o)
        return;
    pushdown(o);
    int d = cmp(o, k);
    if(d == 1)
        k -= size(lc(o)) + 1;
    if(d != -1)
    {
        Node *p = o -> ch[d];
        pushdown(p);
        int d2 = cmp(p, k);
        int k2 = (d2 == 0 ? k : k - size(lc(p)) - 1);
        if(d2 != -1)
        {
            splay(p -> ch[d2], k2);
            if(d == d2)
                rotate(o, d ^ 1);
            else
                rotate(o -> ch[d], d);
        }
        rotate(o, d ^ 1);
    }
}

int a[maxn] = {0}, b[maxn] = {0}, c[maxn] = {0};
Node *table[maxn] = {NULL};
inline bool compare(int x, int y) {return a[x] == a[y] ? x < y : a[x] < a[y];}
void build(Node* &o, int x, int y, Node *fa = NULL)
{
    if(x > y)
        return;
    int m = (x + y) / 2;
    if(!o)
        o = new Node(a[m], fa);
    table[c[m]] = o;
    build(lc(o), x, m - 1, o);
    build(rc(o), m + 1, y, o);
    maintain(o);
}

int ret = 0;
void count(Node* o, bool first = false)
{
    if(first)
    {
        ret += size(lc(o)) + 1;
        if(rev(o))
            ret = size(o) + 1 - ret;
    }
    if(!fa(o))
        return;
    if(rc(fa(o)) == o)
        ret += size(lc(fa(o))) + 1;
    if(rev(fa(o)))
        ret = size(fa(o)) + 1 - ret;
    count(fa(o));
}

void go(Node* &o, int i)
{
    ret = 0;
    count(table[i], true);
    if(i != 1) printf(" ");
    printf("%d", ret + i - 1);
    if(size(o) == 1)
        return;
    splay(o, ret);
    if(lc(o))
        rev(lc(o)) ^= 1;
    if(!rc(o))
        o = lc(o), fa(o) = NULL;
    else if(!lc(o))
        o = rc(o), fa(o) = NULL;
    else
    {
        splay(rc(o), 1);
        fa(lc(o)) = rc(o);
        lc(rc(o)) = lc(o);
        o = rc(o);
        fa(o) = NULL;
        maintain(o);
    }
}

int main()
{
    int n;
    while(read(n), n)
    {
        root = NULL;
        for(int i = 1; i <= n; i++)
            read(a[i]);
        for(int i = 1; i <= n; i++)
            b[i] = i;
        sort(b + 1, b + n + 1, compare);
        for(int i = 1; i <= n; i++)
            c[b[i]] = i;
        build(root, 1, n);
        for(int i = 1; i <= n; i++)
            go(root, i);
        puts("");
    }
    return 0;
}