蜜汁WA

_MLE_自动机 @ 2021-02-24 14:04:18

by _MLE_自动机 @ 2021-02-24 14:04:45

code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 9;

#define gc getchar
inline int read() {
    int c = gc(), t = 1, n = 0;
    while(isspace(c)) { c = gc(); }
    if(c == '-') { t = -1, c = gc(); }
    while(isdigit(c)) { n = n * 10 + c - '0', c = gc(); }
    return n * t;
}
#undef gc

int n,m,broot,ans;

namespace SGT {
    struct node {
        int ls,rs,size,last,same,val;
    }t[N];

    #define ls(x) t[x].ls
    #define rs(x) t[x].rs
    #define alpha 0.75

    int rt[N],crt = 0,cnt = 0;

    bool judge(int u) {
        return (t[u].same && (alpha * (double)t[u].size < (double)max(t[ls(u)].size,t[rs(u)].size) || (double)alpha * t[u].size > (double)t[u].last));
    }

    inline void push_up(int u) {
        t[u].size = t[ls(u)].size + t[rs(u)].size + t[u].same;
        t[u].last = t[ls(u)].last + t[rs(u)].last + t[u].same;
    }

    inline void unfold(int u) {
        if(!u) return;
        unfold(ls(u));
        if(t[u].same) rt[++crt] = u;
        unfold(rs(u)); 
    }

    inline int rebuild(int l,int r) {
        if(l == r) return 0;
        int mid = (l + r) >> 1;
        ls(rt[mid]) = rebuild(l,mid); rs(rt[mid]) = rebuild(mid + 1,r);
        push_up(rt[mid]);
        return rt[mid];
    }

    inline void bal(int &u) {
        crt = 0; unfold(u); u = rebuild(1,crt + 1);
    }

    inline void insert(int &u,int x) {
        if(!u) {
            u = ++cnt;
            if(!broot) broot = 1;
            ls(u) = rs(u) = 0;
            t[u].val = x; t[u].same = t[u].size = t[u].last = 1;
        }else {
            if(t[u].val == x) ++t[u].same;
            else if(t[u].val > x) insert(ls(u),x);
            else insert(rs(u),x);
            push_up(u);
            if(judge(u)) bal(u);
        }
    }

    inline void del(int &u,int x) {
        --t[u].last;
        if(t[u].val == x) --t[u].same;
        else if(t[u].val > x) del(ls(u),x);
        else del(rs(u),x);
        push_up(u);
        if(judge(u)) bal(u);
    }

    inline int rank_up(int u,int x) {
        if(!u) return 1;
        if(t[u].same && x == t[u].val) return t[u].same + t[ls(u)].last + 1;
        else if(t[u].val > x) return rank_up(ls(u),x);
        else return rank_up(rs(u),x) + t[u].same + t[ls(u)].last;
    }

    inline int rank_down(int u,int x) {
        if(!u) return 0;
        if(t[u].same && x == t[u].val) return t[ls(u)].last;
        else if(t[u].val > x) return rank_down(ls(u),x);
        else return rank_down(rs(u),x) + t[u].same + t[ls(u)].last;
    }

    inline int at(int u,int x) {
        if(ls(u) == rs(u)) return t[u].val;
        if(x <= t[ls(u)].last) return at(ls(u),x);
        else if(x > t[ls(u)].last && t[ls(u)].last + t[u].same >= x) return t[u].val;
        else return at(rs(u),x - t[u].same - t[ls(u)].last);
    }
}; using namespace SGT;
//以上都没有问题

int opt,x,last;

int main() {
    n = read(); m = read();
    for(int i = 1;i <= n;i++) insert(broot,read());
    for(int i = 1;i <= m;i++) {
        opt = read(); x = read() ^ last;
        if(opt == 1) insert(broot,x);
        if(opt == 2) del(broot,x);
        if(opt <= 2) continue;
        if(opt == 3) last = rank_down(broot,x) + 1;
        if(opt == 4) last = at(broot,x);
        if(opt == 5) last = at(broot,rank_down(broot,x));
        if(opt == 6) last = at(broot,rank_up(broot,x));
        ans ^= last;
    }
    printf("%d\n",ans);
    return 0;
}

by _MLE_自动机 @ 2021-02-24 14:25:03

问题解决，此贴终结
这年头连RE都判成WA了……