指针老是RE

P3391 【模板】文艺平衡树

Cyhlnj @ 2017-07-11 19:28:33

# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <string.h>

define ll long long

define RG register

define IL inline

define UN unsigned

# define mem(a, b) memset(a, b, sizeof(a))
# define min(a, b) ((a) < (b)) ? (a) : (b)
# define max(a, b) ((a) > (b)) ? (a) : (b)
using namespace std;
IL int Get(){
    char c = '!'; int z = 1, num = 0;
    while(c != '-' && (c < '0' || c > '9'))
        c = getchar();
    if(c == '-')
        z = -1, c = getchar();
    while(c >= '0' && c <= '9')
        num = num * 10 + c - '0', c = getchar();
    return num * z;
}
struct tree{
    tree *fa, *ch[2];
    int size, lazy, pos;
    IL tree(){
        fa = ch[0] = ch[1] = NULL;
        pos = lazy = size = 0;
    }
    IL void Pushdown(){
        if(!lazy) return;
        lazy = 0;
        if(ch[1] == NULL && ch[0] == NULL) return;
            if(ch[0] != NULL) ch[0] -> lazy ^= 1;
        if(ch[1] != NULL) ch[1] -> lazy ^= 1;
        swap(ch[0], ch[1]);
    }
} *root;
int n;
IL int Size(RG tree *x){
    return (x == NULL) ? 0 : x -> size + 1;
}
IL void Updata(RG tree *x){
    if(x == NULL) return;
    x -> size = Size(x -> ch[0]) + Size(x -> ch[1]);
}
IL void Dfs(RG tree *x){
    if(x == NULL) return;
    x -> Pushdown();
    Dfs(x -> ch[0]);
    if(x -> pos && x -> pos <= n)
        printf("%d ", x -> pos);
    Dfs(x -> ch[1]);
}
IL void Rot(RG tree *x, RG int i){ //0为左旋,1为右旋
    RG tree *y = x -> fa;
    x -> Pushdown(); y -> Pushdown();
    y -> ch[!i] = x -> ch[i];
    if(x -> ch[i] != NULL) x -> ch[i] -> fa = y;
    x -> fa = y -> fa;
    if(y -> fa != NULL)
        if(y -> fa -> ch[0] == y) y -> fa -> ch[0] = x;
        else y -> fa -> ch[1] = x;
    x -> ch[i] = y; y -> fa = x; Updata(y);
    if(y == root) root = x;
}
IL void Splay(RG tree *x, RG tree *f){
    while(x -> fa != f){
        x -> Pushdown();
        if(x -> fa -> fa == f)
            if(x == x -> fa -> ch[0]) Rot(x, 1);
            else Rot(x, 0);
        else{
            RG tree *y = x -> fa, *z = y -> fa;
            if(z -> ch[0] == y)
                if(y -> ch[0] == x) Rot(y, 1), Rot(x, 1);
                else Rot(x, 0), Rot(x, 1);
            else
                if(y -> ch[1] == x) Rot(y, 0), Rot(x, 0);
                else Rot(x, 1), Rot(x, 0);
        }
    }
     Updata(x);
}
IL tree *Build(RG int l, RG int r, RG tree *f){
    RG int mid = (l + r) >> 1;
    tree *x = new tree;
    x -> pos = mid;
    x -> fa = f;
    if(mid > l) x -> ch[0] = Build(l, mid - 1, x);
    if(mid < r) x -> ch[1] = Build(mid + 1, r, x);
    Updata(x);
    return x;
}
IL void Find(RG int num, RG tree *f){
    RG tree *x = root;
    while(2333){
        x -> Pushdown();
        RG int l = Size(x -> ch[0]);
        if(num < l) x = x -> ch[0];
        else if(num == l) break;
        else{
            num -= (l + 1);
            x = x -> ch[1];
        }
    }
    Splay(x, f);
}
IL void Turn(){
    RG int l = Get(), r = Get();
    Find(l - 1, NULL); Find(r + 1, root);
    root -> ch[1] -> ch[0] -> lazy ^= 1;
}
int main(){
    n = Get();
    RG int m = Get();
    root = Build(0, n + 1, NULL);
    while(m--) Turn();
    Dfs(root);
    printf("\n");
    return 0;
}

|