splay90求助

提交记录

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2e6;
const int INF = 0x7fffffff;

int n, m, last, ans, tot, root;
int val[N], cnt[N], size[N], fa[N], ch[N][2];

int newnode(int x) {
    val[++tot] = x;
    cnt[tot] = size[tot] = 1;
    return tot;
}

void update(int x) {
    size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
}

bool id(int x) {
    return x == ch[fa[x]][1];
}

void connect(int x, int y, bool k) {
    ch[x][k] = y;
    fa[y] = x;
}

void rotate(int x) {
    int y = fa[x], z = fa[y];
    bool k = id(x);
    connect(z, x, id(y));
    connect(y, ch[x][k ^ 1], k);
    connect(x, y, k ^ 1);
    update(y);
    update(x);
}

void splay(int x, int to) {
    while (fa[x] != to) {
        int y = fa[x];
        if (fa[y] != to) id(x) ^ id(y) ? rotate(x) : rotate(y);
        rotate(x);
    }
    if (to == 0) root = x;
}

void find(int x) {
    int u = root;
    while (val[u] != x && ch[u][x > val[u]]) u = ch[u][x > val[u]];
    splay(u, 0);
}

void insert(int x) {
    if (!root) {
        root = newnode(x);
        return;
    }
    int u = root;
    while (val[u] != x && ch[u][x > val[u]]) u = ch[u][x > val[u]];
    if (val[u] == x) {
        cnt[u]++;
        splay(u, 0);
    } else {
        connect(u, newnode(x), x > val[u]);
        splay(ch[u][x > val[u]], 0);
    }
}

void erase(int x) {
    if (!root) return;
    find(x);
    if (!root || val[root] != x) return;
    if (cnt[root] > 1) {
        cnt[root]--;
        size[root]--;
        return;
    }
    int u = ch[root][0];
    if (!u) {
        root = ch[root][1];
        fa[root] = 0;
        return;
    }
    while (ch[u][1]) u = ch[u][1];
    splay(u, root);
    connect(u, ch[root][1], 1);
    root = u;
    fa[root] = 0;
    update(root);
}

int rank(int x) {
    find(x);
    int ls = size[ch[root][0]];
    return (val[root] < x ? ls + cnt[root] : ls) + 1;
}

int kth(int x) {
    int u = root;
    while (1) {
        if (x <= size[ch[u][0]]) u = ch[u][0];
        else if (x > size[ch[u][0]] + cnt[u]) {
            x -= size[ch[u][0]] + cnt[u];
            u = ch[u][1];
        } else break;
    }
    splay(u, 0);
    return val[u];
}

int pre(int x) {
    find(x);
    if (val[root] < x) return val[root];
    int u = ch[root][0];
    if (!u) return -INF;
    while (ch[u][1]) u = ch[u][1];
    splay(u, 0);
    return val[u];
}

int nxt(int x) {
    find(x);
    if (val[root] > x) return val[root];
    int u = ch[root][1];
    if (!u) return INF;
    while (ch[u][0]) u = ch[u][0];
    splay(u, 0);
    return val[u];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, a; i <= n; i++) {
        scanf("%d", &a);
        insert(a);
    }
    for (int i = 1, opt, x; i <= m; i++) {
        scanf("%d%d", &opt, &x);
        x ^= last;
        if (opt == 1) insert(x);
        if (opt == 2) erase(x);
        if (opt == 3) {
            last = rank(x);
            ans ^= last;
        }
        if (opt == 4) {
            last = kth(x);
            ans ^= last;
        }
        if (opt == 5) {
            last = pre(x);
            ans ^= last;
        }
        if (opt == 6) {
            last = nxt(x);
            ans ^= last;
        }
    }
    printf("%d", ans);
    return 0;
}