普通平衡树加强版 WA on #11求调

可能并不是 splay 少了的问题。因为把双旋里面全都改成 rotate(x) 之后会 WA。

#include <iostream>
#include <cstring>
#include <cstdio>
#define int long long

using namespace std;

const int N = 1200010;

int n, m, ans, fa[N], sz[N], val[N];
int ch[N][2], cnt[N], idx, root, last;
#define ls ch[x][0]
#define rs ch[x][1]
void pushup(int x) { sz[x] = sz[ls] + sz[rs] + cnt[x]; }
void rotate(int x) {
    int y = fa[x], z = fa[y], k = ch[y][1] == x, w = ch[x][k ^ 1];
    if (z) ch[z][ch[z][1] == y] = x; fa[x] = z;
    fa[fa[ch[ch[x][k ^ 1] = y][k] = w] = y] = x;
    pushup(y); pushup(x);
}
void splay(int x, int k = 0) {
    for (int y, z; fa[x] != k; rotate(x)) {
        y = fa[x], z = fa[y];
        if (z ^ k) rotate((ch[y][1] == x) ^ (ch[z][1] == y) ? x : x);
    } if (!k) root = x;
}
void insert(int v, int x = root, int p = 0) {
    while (x && val[x] != v) p = x, x = ch[x][v > val[x]];
    if (x) cnt[x] ++ ; else {
        x = ++ idx; if (p) ch[p][v > val[p]] = x;
        sz[x] = cnt[x] = 1, val[x] = v; fa[x] = p;
    } splay(x);
}
void find(int v, int x = root) {
    if (!x) return;
    while (ch[x][v > val[x]] && v != val[x])
        x = ch[x][v > val[x]]; splay(x);
}
int pn(int v, int tp, int x = root) {
    find(v); x = root; if (!tp and val[x] < v) return splay(x), x;
    if (tp and val[x] > v) return splay(x), x; x = ch[x][tp];
    while (ch[x][tp ^ 1]) x = ch[x][tp ^ 1]; return splay(x), x;
}
void remove(int v) {
    int pre = pn(v, 0), nxt = pn(v, 1);
    splay(pre); splay(nxt, pre);
    if (cnt[ch[nxt][0]] > 1) cnt[ch[nxt][0]] -- ;
    else ch[nxt][0] = 0; splay(nxt);
}
int kth(int k, int x = root) {
    if (sz[x] < k) return 0;
    while (true) {
        if (sz[ls] >= k) x = ls;
        else if (sz[ls] + cnt[x] >= k) return splay(x), val[x];
        else k -= sz[ls] + cnt[x], x = rs;
    }
}
int rk(int v) {
    find(v); int x = root;
    return sz[ls] + cnt[x] * (val[x] < v);
}
signed main() {
    scanf("%lld%lld", &n, &m);
    insert(1e18), insert(-1e18);
    for (int i = 1, a; i <= n; i ++ )
        scanf("%lld", &a), insert(a);
    while (m -- ) {
        int op, x;
        scanf("%lld%lld", &op, &x); x ^= last;
        if (op == 1) insert(x);
        if (op == 2) remove(x);
        if (op == 3) ans ^= (last = rk(x));
        if (op == 4) ans ^= (last = kth(x + 1));
        if (op == 5) ans ^= (last = val[pn(x, 0)]);
        if (op == 6) ans ^= (last = val[pn(x, 1)]);
    } printf("%lld\n", ans); return 0;
}