hdu1890 伸展树区间翻转复习

题意： 给你n个数,每次先输出第i大的数的位置(如果有多个，选下标小的那个)，然后每次将第i个位置到第i大的数所在位置之间的数进行翻转。

思路：输入的数组可能有多个相同的值，我们可以进行两次排序把数组的值变为0---n-1(表示第几大)。

在建伸展树的时候我们可以顺便用pos[i]记录第i大的数的节点指针。

对于第i次操作，我们用flip记录翻转标记，每次先把第i大的节点pos[i]旋转到根，那么它的位置为i+左儿子的个数+1。然后左儿子打上翻转标记，最后删除根。

注意：下放懒惰标记时只要交换左右儿子的节点标号就可以了，也正因为这个原因， 

下放函数的位置记得要放在没有引用任何左右儿子信息之前， 这跟区间其它操作最大的区别。

这次用指针写的，注意虚节点null 不能down， 因为null的左右儿子都为null  不能swap

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node;
node *null, *root;
struct node {
    node *c[2], *fa;
    int sz, id;
    bool flip;
    bool d() {
        return fa->c[1] == this;
    }
    void fix(int d, node *x) {
        c[d] = x; x->fa = this;
    }
    void rot() {
        node *y = fa, *z = y->fa;
        int f = d();
        z->fix(y->d(), this);
        y->fix(f, c[!f]);
        fix(!f, y);
        y->up();
    }
    void splay(node *g) {
        while(fa != g) {
            node *y = fa, *z = y->fa;
            z->down(), y->down(),down();
            if(z == g) rot();
            else if(y->d() == d())
                y->rot(), rot();
            else 
                rot(),rot();
        }
        up();
        if(g == null) root = this;
    }
    void up() {
        sz = c[0]->sz + c[1]->sz+1;
    }
    void down() {
        if(this==null) return;
        if(flip) {
            c[0]->flip ^= 1;
            c[1]->flip ^= 1;
            swap(c[0], c[1]);
            flip = 0;
        }
    }
    void out() {//debug
        printf("v%d ls%d rs%d lsz%d rsz%d fa%d\n", id, c[0]->id, c[1]->id, c[0]->sz, c[1]->sz, fa->id);
    }
};
const int maxn = 100005;
struct data {
    int val, id;
    bool operator<(const data &t) const {
        return id < t.id;
    }
}a[maxn];
bool cmp(const data &a, const data &b) {
    return a.val < b.val || (a.val == b.val && a.id < b.id);
}
struct splayTree {
    node mem[maxn];
    int tot;
    node *pos[maxn];
    node* newNode(node *fa=null) {
        node *x = &mem[tot];
        x->c[0] = x->c[1] = null, x->fa = fa;
        x->sz = 1, x->id = tot++, x->flip = 0;
        return x;    
    }
    void build(node *&x, int l, int r, node *fa) {
        if( l > r ) return;
        int m = (l + r) >> 1;
        x = newNode(fa);
        pos[a[m].val] = x;
        build(x->c[0], l, m-1, x);
        build(x->c[1], m+1, r, x);
        x->up();
    }
    void rto(int k, node *g) {
        node *x = root;
        while(true) {
            x->down();
            int v = x->c[0]->sz+1;
            if(v == k) break;
            if(k >  v) {
                k -= v;
                x = x->c[1];
            }else x = x->c[0];
        }
        x->splay(g);
    }
    void init(int n) {
        tot = 0;
        int i, j;
        for(i = 0; i < n; i++) {
            scanf("%d", &a[i].val);
            a[i].id = i;
        }
        sort(a, a+n, cmp);
        for(i = 0; i < n; i++)
            a[i].val = i;
        sort(a, a+n);
        null = newNode(), null->sz = 0;
        root = null;
        build(root, 0, n-1, null);
    }
    void show(node *o) {//debug
        if(o==null) return;    
        o->down();
        o->out();
        show(o->c[0]);
        show(o->c[1]);
    }
    void show() {//debug
        printf("root = %d\n", root->id);
        show(root);
        puts("~~~~~~");
    }
    void work(int n) {
        int i;
        for(i = 0; i < n-1; i++) {
            pos[i]->splay(null);
            printf("%d ", root->c[0]->sz+i+1);
            root->down(); 
            root->c[0]->flip^=1;
            root->c[0]->down();
            if(root->c[0]!=null) { 
                rto(root->c[0]->sz, root);
                node *x = root;
                root = x->c[0];
                root->fa = null;
                root->fix(1, x->c[1]);
            }else {
                root = root->c[1];
                root->fa = null;
            }
            root->up();
        }
        printf("%d\n", n);
    }
}spt;
int main() {
    int i, j, n;
    while(~scanf("%d", &n) && n) {
        spt.init(n);
        spt.work(n);
    }
    return 0;
}

hdu1890 伸展树区间翻转复习

原文：http://blog.csdn.net/auto_ac/article/details/19262815