BZOJ3223——Tyvj 1729 文艺平衡树

1、题目大意：维护序列，只有区间翻转这个操作

2、分析：splay的经典操作就是实现区间翻转，就是在splay中有一个标记，表示这个区间被翻转了

然后就是记得各种的操作访问某个点时，记得下传，顺便交换一下左右子树的左右子树（我语文不好

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node{
    Node *ch[2];
    int f, v, s;
    int cmp(int x){
        if(x < v) return 0;
        else if(x == v) return -1;
        else return 1;
    }
    int cmp1(int x){
        int k = 1;
        if(ch[0]) k += ch[0] -> s;
        if(x < k) return 0;
        else if(x == k) return -1;
        else if(x > k) return 1;
    }
    void maintain(){
        s = 1;
        if(ch[0]) s += ch[0] -> s;
        if(ch[1]) s += ch[1] -> s;
    }
    void pushdown(){
        if(f == 1){
            if(ch[0] != NULL){
                ch[0] -> f ^= 1;
                swap(ch[0] -> ch[0], ch[0] -> ch[1]);
            }
            if(ch[1] != NULL){
                ch[1] -> f ^= 1;
                swap(ch[1] -> ch[0], ch[1] -> ch[1]);
            }
            f = 0;
        }
    }
};
struct splay_tree{
    Node ft[2000000];
    Node *root;
    int a[200000], tot;
    void rotate(Node* &o, int d){
        Node *k = o -> ch[d ^ 1];
        k -> pushdown();
        o -> ch[d ^ 1] = k -> ch[d];
        k -> ch[d] = o;
        o -> maintain();
        k -> maintain();
        o = k;
    }
    void splay(Node* &o, int k){
        if(!o) return;
        o -> pushdown();
        if(o -> ch[0]) o -> ch[0] -> pushdown();
        if(o -> ch[1]) o -> ch[1] -> pushdown();
        int d = o -> cmp1(k);
        if(d == 1 && o -> ch[0]) k = k - o -> ch[0] -> s - 1;
        else if(d == 1) k --;
        if(d != -1){
            Node* w = o -> ch[d];
            int d2 = w -> cmp1(k);
            int k2 = k;
            if(d2 == 1){
                k2 --;
                if(w -> ch[0]) k2 -= w -> ch[0] -> s;
            }
            if(d2 != -1){
                splay(w -> ch[d2], k2);
                if(d == d2) rotate(o, d ^ 1);
                else rotate(o -> ch[d], d);
            }
            rotate(o, d ^ 1);
        }
        return;
    }
    Node* merge(Node *left, Node *right){
        if(left == NULL) return right;
        if(right == NULL) return left;
        splay(left, left -> s);
        left -> ch[1] = right;
        left -> maintain();
        return left;
    }
    void split(Node* &o, int k, Node* &left, Node* &right){
        if(k == 0){
            left = NULL;
            right = o;
            return;
        }
        splay(o, k);
        left = o;
        right = o -> ch[1];
        left -> ch[1] = NULL;
        left -> maintain();
        return;
    }
    void flip(int l, int r){
        Node *left, *mid, *right;
        split(root, l - 1, left, mid);
        split(mid, r - l + 1, mid, right);
        swap(mid -> ch[0], mid -> ch[1]);
        mid -> f ^= 1;
        root = merge(left, merge(mid, right));
    }
    int value(int l){
        Node *left, *mid, *right;
        split(root, l - 1, left, mid);
        split(mid, 1, mid, right);
        int ret = mid -> v;
        root = merge(left, merge(mid, right));
        return ret;
    }
    void insert(Node* &o, int l, int r){
        if(r < l) return;
        int mid = (l + r) / 2;
        o = &ft[tot]; tot ++;
        o -> ch[0] = o -> ch[1] = NULL;
        o -> v = mid;
        o -> f = 0;
        if(l != r){
            insert(o -> ch[0], l, mid - 1);
            insert(o -> ch[1], mid + 1, r);
        }
        o -> maintain();
        return;
    }
} wt;
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) wt.a[i] = i;
    wt.insert(wt.root, 1, n);
    for(int i = 1; i <= m; i ++){
        int l, r;
        scanf("%d%d", &l, &r);
        wt.flip(l, r);
    }
    for(int i = 1; i <= n; i ++){
        printf("%d ", wt.value(i));
    }
    return 0;
}

巴特西

BZOJ3223——Tyvj 1729 文艺平衡树

最新文章

热门文章