没错还是我

贴子 1 号
贴子 2 号
最新求助，Splay 玄学 RE

#include <cstdio>
#include <cctype>
using namespace std;

void readint(int &v) {
    char c;
    while (!isdigit(c = getchar())) ;
    v = c & 15;
    while (isdigit(c = getchar())) v = v*10 + (c & 15);
}

inline int getint() {
    int x;
    readint(x);
    return x;
}

struct elem {
    int val, cnt, siz, fa;
    int sons[2];
} a[1001000];

int rt;
int ncnt;

inline void Pushup(int u) {
    a[u].siz = a[a[u].sons[0]].siz + a[a[u].sons[1]].siz + a[u].cnt;
}

inline void Clr(int u) {
    a[u].val = a[u].cnt = a[u].siz = a[u].fa = a[u].sons[0] = a[u].sons[1] = 0;
}

inline void Rotate(int u) {
    int tmp1 = a[u].fa;
    int tmp2 = a[tmp1].fa;
    int dir = u == a[tmp1].sons[1];
    a[tmp1].sons[dir] = a[u].sons[!dir];
    a[a[u].sons[!dir]].fa = tmp1;
    a[u].sons[!dir] = tmp1;
    a[tmp1].fa = u;
    a[u].fa = tmp2;
    if (tmp2) a[tmp2].sons[tmp1 == a[tmp2].sons[1]] = u;
    Pushup(tmp1);
    Pushup(u);
}

void Splay(int u) {
    if (u) {
        for (int i; (i = a[u].fa); Rotate(u))
            if (a[i].fa)
                Rotate((u == a[a[u].fa].sons[1]) == (i == a[a[i].fa].sons[1]) ?
                        i : u);
        rt = u;
    }
}

void Ins(int v) {
    if (!rt) {
        a[rt = ++ncnt].val = v;
        a[rt].siz = a[rt].cnt = 1;
        return;
    }
    int tmp1 = rt, tmp2 = 0;
    while (1) {
        if (a[tmp1].val == v) {
            ++a[tmp1].cnt;
            ++a[tmp1].siz;
            Pushup(tmp2);
            Splay(tmp1);
            return;
        }
        tmp2 = tmp1;
        tmp1 = a[tmp1].sons[a[tmp1].val < v];
        if (!tmp1) {
            a[++ncnt].val = v;
            a[a[tmp2].sons[a[tmp2].val < v] = ncnt].siz = a[ncnt].cnt = 1;
            a[ncnt].fa = tmp2;
            ++a[tmp2].siz;
            Splay(ncnt);
            return;
        }
    }
}

int Getrnk(int v) {
    int ret = 1;
    int tmp = rt;
    while (1)
        if (v < a[tmp].val) {
            tmp = a[tmp].sons[0];
        } else {
            ret += a[a[tmp].sons[0]].siz;
            if (v == a[tmp].val || a[tmp].sons[1] == 0) {
                Splay(tmp);
                return ret + (v != a[tmp].val) * a[tmp].cnt;
            }
            ret += a[tmp].cnt;
            tmp = a[tmp].sons[1];
        }
}

int Getrtpresuc(bool flg) {
    int tmp = a[rt].sons[flg];
    while (a[tmp].sons[!flg]) tmp = a[tmp].sons[!flg];
    return tmp;
}

inline void Del(int v) {
    Getrnk(v);
    if (a[rt].cnt > 1) {
        --a[rt].cnt;
        --a[rt].siz;
        return;
    }
    if (a[rt].siz == 1) {
        Clr(rt);
        rt = 0;
        return;
    }
    int tmp = rt;
    if (a[rt].sons[0] == 0 || a[rt].sons[1] == 0) {
        rt = a[rt].sons[!a[rt].sons[0]];
        a[rt].fa = 0;
        Clr(tmp);
        return;
    }
    int pre = Getrtpresuc(false);
    Splay(pre);
    a[rt].sons[1] = a[tmp].sons[1];
    a[a[tmp].sons[1]].fa = rt;
    Clr(tmp);
    --a[rt].siz;
}

int Getnum(int v) {
    int tmp = rt;
    while (1)
        if (a[tmp].sons[0] > 0 && v <= a[a[tmp].sons[0]].siz) {
            tmp = a[tmp].sons[0];
        } else {
            v -= a[a[tmp].sons[0]].siz + a[tmp].cnt;
            if (v <= 0) return a[tmp].val;
            tmp = a[tmp].sons[1];
        }
}

inline int Getpresuc(int v, bool flg) {
    Ins(v);
    int ret = a[Getrtpresuc(flg)].val;
    Del(v);
    return ret;
}

int main() {
    int n, m;
    readint(n);
    readint(m);
    while (n--) Ins(getint());
    int ans = 0;
    int Last = 0;
    while (m--) {
        int opt;
        readint(opt);
        switch (opt) {
            case 1: Ins(getint() ^ Last); break;
            case 2: Del(getint() ^ Last); break;
            case 3: Last = Getrnk(getint() ^ Last); break;
            case 4: Last = Getnum(getint() ^ Last); break;
            default: Last = Getpresuc(getint() ^ Last, opt - 5);
        }
        if (opt > 2) ans ^= Last;
    }
    printf("%d\n", ans);
    return 0;
}