MnZn求助，指针旋转 Treap ，RE #10、#18，92pts

rt，这题应该不会卡指针吧...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int n, m;
int res_and_last, ans;

const int LF = 0, RT = 1;
struct Tree
{
    int size, val, cnt, rank;
    Tree *ch[2];

    Tree (int k) : val(k), cnt(1), size(1)
    {
        ch[0] = ch[1] = NULL;
        rank = rand();
    }

    void upd_size()
    {
        size = cnt;
        if (ch[0] != NULL) size += ch[0]->size;
        if (ch[1] != NULL) size += ch[1]->size;
    }
};
Tree *root = NULL;
int Q_pre, Q_sub;

inline int read()
{
    int x = 0; char ch = getchar();
    while ( !isdigit(ch) ) ch = getchar();
    while ( isdigit(ch) ) { x = x * 10 + (ch - '0'); ch = getchar(); }
    return x;
}

void _rotate (Tree *&cur, int dir)
{
    Tree *tmp = cur->ch[!dir];
    cur->ch[!dir] = tmp->ch[dir];
    tmp->ch[dir] = cur;
    tmp->upd_size(), cur->upd_size();
    cur = tmp;
}
void insert (Tree *&cur, int k)
{
    if (cur == NULL)
    {
        cur = new Tree(k);
        return;
    }
    if (k == cur->val) cur->cnt ++, cur->size ++;
    else if (k < cur->val)
    {
        insert (cur->ch[0], k);
        if (cur->ch[0]->rank < cur->rank) _rotate(cur, RT);
        cur->upd_size();
    }
    else
    {
        insert (cur->ch[1], k);
        if (cur->ch[1]->rank < cur->rank) _rotate(cur, LF);
        cur->upd_size();
    }
}
void del (Tree *&cur, int k)
{
    if (k == cur->val)
    {
        if (cur->cnt > 1) { cur->cnt --, cur->size --; return; }
        int flag = 0;
        flag |= ( (cur->ch[0] != NULL) << 1);
        flag |= (cur->ch[1] != NULL);
        Tree *tmp = cur;
        if (!flag) { cur = NULL; delete cur; }
        else if (flag == 1) { cur = tmp->ch[1]; delete tmp; }
        else if (flag == 2) { cur = tmp->ch[0]; delete tmp; }
        else if (flag == 3)
        {
            int dir = cur->ch[0]->rank < cur->ch[1]->rank ? RT : LF;
            _rotate (cur, dir);
            del (cur->ch[dir], k);
            cur->upd_size();
        }
    }
    else if (k < cur->val)
    {
        del (cur->ch[0], k);
        cur->upd_size();
    }
    else
    {
        del (cur->ch[1], k);
        cur->upd_size();
    }
}
int query_rank (Tree *cur, int k)
{
    int ls_size = cur->ch[0] == NULL ? 0 : cur->ch[0]->size;
    if (k == cur->val) return ls_size + 1;
    else if (k < cur->val)
    {
        if (cur->ch[0] != NULL) return query_rank(cur->ch[0], k);
        else return 1;
    }
    else
    {
        if (cur->ch[1] != NULL) return ls_size + cur->cnt + query_rank(cur->ch[1], k);
        else return cur->size + 1;
    }
}
int query_num (Tree *cur, int rk)
{
    int ls_size = cur->ch[0] == NULL ? 0 : cur->ch[0]->size;
    if (rk <= ls_size) return query_num(cur->ch[0], rk);
    else if (rk > ls_size + cur->cnt) return query_num(cur->ch[1], rk - ls_size - cur->cnt);
    else return cur->val;
}
int query_pre (Tree *cur, int k)
{
    if (k <= cur->val)
    {
        if (cur->ch[0] != NULL) return query_pre(cur->ch[0], k);
    }
    else
    {
        Q_pre = cur->val;
        if (cur->ch[1] != NULL) query_pre(cur->ch[1], k);
        return Q_pre;
    }
    return -114514;
}
int query_sub (Tree *cur, int k)
{
    if (k >= cur->val)
    {
        if (cur->ch[1] != NULL) return query_sub(cur->ch[1], k);
    }
    else
    {
        Q_sub = cur->val;
        if (cur->ch[0] != NULL) query_sub(cur->ch[0], k);
        return Q_sub;
    }
    return 1919810;
}
void work()
{
    n = read(); m = read();
    while (n --) insert (root, read() );
    while (m --)
    {
        int opt, x;
        opt = read(); x = read() ^ res_and_last;
        if (opt == 1) insert(root, x);
        else if (opt == 2) del(root, x);
        if (opt <= 2) continue;
        else if (opt == 3) res_and_last = query_rank(root, x);
        else if (opt == 4) res_and_last = query_num(root, x);
        else if (opt == 5) res_and_last = query_pre(root, x);
        else res_and_last = query_sub(root, x);
        ans ^= res_and_last;
    }
    printf ("%d\n", ans);
}

int main()
{
    work();
    return 0;
}