萌新求助,fhq treap 0分
查看原帖
萌新求助,fhq treap 0分
181566
after_the_end楼主2020/8/11 18:41

下面是错误源代码

#include<bits/stdc++.h>
using namespace std;
#define re register
int cnt, root, n, opt, last, ans, m, pot;
struct tree
{
    int l, r, val, key, size;
} fhq[2000001];
inline int newnode(int val){
    fhq[++cnt].val = val;
    fhq[cnt].key = rand();
    fhq[cnt].size = 1;
    return cnt;
}
inline void update(int now){
    fhq[now].size = fhq[fhq[now].l].size + fhq[fhq[now].r].size + 1;
}
int split(int now,int val,int &x,int &y){
    if(!now)
        x = y = 0;
    else{
        if(val>=fhq[now].val){
            x = now;
            split(fhq[now].r, val, fhq[now].r, y);
        }
        else{
            y = now;
            split(fhq[now].l, val, x, fhq[now].l);
        }
        update(now);
    }
}
int merge(int x,int y){
    if(!x||!y)
        return x | y;
    if(fhq[x].key>fhq[y].key){
        fhq[x].r = merge(fhq[x].r, y);
        update(x);
        return x;
    }
    else{
        fhq[y].l = merge(x, fhq[y].l);
        update(y);
        return y;
    }
}
int x, y, z;
inline void ins(int val){
    split(root, val, x, y);
    root = merge(merge(x, newnode(val)), y);
}
inline void del(int val){
    split(root, val, x, z);
    split(x, val - 1, x, y);
    y = merge(fhq[y].l, fhq[y].r);
    root = merge(merge(x, y), z);
}
inline void getrank(int val){
    split(root, val-1, x, y);
    last = fhq[x].size + 1;
    ans ^= last;
    root = merge(x, y);
}
inline void getnum(int rank){
    int now = root;
    while(now){
        if(fhq[fhq[now].l].size+1==rank){
            break;
        }
        else if(fhq[fhq[now].l].size>=rank){
            now = fhq[now].l;
        }
        else{
            rank -= fhq[fhq[now].l].size+1;
            now = fhq[now].r;
        }
    }
    last = fhq[now].val;
    ans ^= last;
}
inline void pre(int val){
    split(root, val - 1, x, y);
    int now = x;
    while(fhq[now].r){
        now = fhq[now].r;
    }
    last = fhq[now].val;
    ans ^= last;
    merge(x, y);
}
inline void nxt(int val){
    split(root, val, x, y);
    int now = y;
    while(fhq[now].l){
        now = fhq[now].l;
    }
    last = fhq[now].val;
    ans ^= last;
    merge(x, y);
}
int main(){
    srand(time(0));
    scanf("%d%d", &n, &m);
    int asd;
    for (re int i = 1; i <= n;++i){
        scanf("%d", &asd);
        ins(asd);
    }
    for (re int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &opt, &pot);
        pot ^= last;
        if (opt == 1)
        {
            ins(pot);
        }
        if (opt == 2)
        {
            del(pot);
        }
        if (opt == 3)
        {
            getrank(pot);
        }
        if (opt == 4)
        {
            getnum(pot);
        }
        if (opt == 5)
        {
            pre(pot);
        }
        if (opt == 6)
        {
            nxt(pot);
        }
    }
    printf("%d", ans);
}

下面是评测结果

2020/8/11 18:41
加载中...