求助 Splay

P3391 【模板】文艺平衡树

cancan123456 @ 2022-02-12 22:22:57

#include <cstdio>
using namespace std;
const int N = 100005;
int v[N], ch[N][2], fa[N];
int rev[N];
int root, tot;
void LeftRotate(int x) {
    int y = ch[x][1], z = fa[x];
    ch[x][1] = ch[y][0];
    if (ch[x][1] != 0) {
        fa[ch[x][1]] = x;
    }
    fa[y] = z;
    if (z != 0) {
        if (ch[z][0] == x) {
            ch[z][0] = y;
        } else {
            ch[z][1] = y;
        }
    }
    fa[x] = y;
    ch[y][0] = x;
}
void RightRotate(int x) {
    int y = ch[x][0], z = fa[x];
    ch[x][0] = ch[y][1];
    if (ch[y][1] != 0) {
        fa[ch[y][1]] = x;
    }
    fa[y] = z;
    if (z != 0) {
        if (ch[z][0] == x) {
            ch[z][0] = y;
        } else {
            ch[z][1] = y;
        }
    }
    fa[x] = y;
    ch[y][1] = x;
}
void Rotate(int x) {
    if (ch[fa[x]][0] == x) {
        RightRotate(fa[x]);
    } else {
        LeftRotate(fa[x]);
    }
}
void Splay(int x, int goal_father = 0) {
    while (fa[x] != goal_father) {
        int y = fa[x];
        int z = fa[y];
        if (z != goal_father) {
            if ((ch[y][0] == x && ch[z][0] == y) || (ch[y][1] == x && ch[z][1] == y)) {
                Rotate(y);
            } else {
                Rotate(x);
            }
        }
        Rotate(x);
    }
    if (goal_father == 0) {
        root = x;
    }
}
int Find(int x) {
    int p = root;
    while (true) {
        if (v[p] == x) {
            return p;
        } else if (x < v[p]) {
            p = ch[p][0];
        } else {
            p = ch[p][1];
        }
    }
}
void Insert(int x) {
    if (root == 0) {
        tot++;
        v[tot] = x;
        root = tot;
    } else {
        int cur = root, f = 0;
        while (true) {
            if (v[cur] == x) {
                break;
            }
            f = cur;
            if (x < v[cur]) {
                if (ch[cur][0] == 0) {
                    tot++;
                    v[tot] = x;
                    fa[tot] = f;
                    ch[f][0] = tot;
                    cur = tot;
                    break;
                } else {
                    cur = ch[cur][0];
                }
            } else {
                if (ch[cur][1] == 0) {
                    tot++;
                    v[tot] = x;
                    fa[tot] = f;
                    ch[f][1] = tot;
                    cur = tot;
                    break;
                } else {
                    cur = ch[cur][1];
                }
            }
        }
        Splay(cur);
    }
}
int build(int l, int r, int f) {
    if (l > r) {
        return 0;
    }
    int p = ++tot;
    int mid = (l + r) / 2;
    fa[p] = f;
    v[p] = mid;
    ch[p][0] = build(l, mid - 1, p);
    ch[p][1] = build(mid + 1, r, p);
    return p;
}
void swap(int & a, int & b) {
    a ^= b ^= a ^= b;
}
int n;
void print(int p = root) {
    if (rev[p] == 1) {
        rev[p] ^= 1;
        swap(ch[p][0], ch[p][1]);
        rev[ch[p][0]] ^= 1;
        rev[ch[p][1]] ^= 1;
    }
    if (ch[p][0] != 0) {
        print(ch[p][0]);
    }
    if (p != 0 && v[p] != 0 && v[p] != n + 1) {
        printf("%d ", v[p]);
    }
    if (ch[p][1] != 0) {
        print(ch[p][1]);
    }
}
int main() {
    int m;
    scanf("%d %d", &n, &m);
    root = build(0, n + 1, 0);
    for (int l, r, i = 1; i <= m; i++) {
        scanf("%d %d", &l, &r);
        Splay(Find(l - 1), 0);
        Splay(Find(r + 1), root);
        rev[ch[ch[root][1]][0]] ^= 1;
    }
    print();
    return 0;
}

样例过了,WA 成 0 分。


|