蒟蒻求助

虫洞吞噬者 @ 2022-09-05 21:54:57

by 虫洞吞噬者 @ 2022-09-05 21:55:31

#include<bits/stdc++.h>
using namespace std;
int rt,tot,ans,last;
struct node{
    int ls,rs,val,key;
    int cnt,siz;
}tree[2000010];
#define lc tree[id].ls
#define rc tree[id].rs
void pushup(int id)
{
    tree[id].siz=tree[lc].siz+tree[rc].siz+tree[id].cnt;
}
void lf(int &id)
{
    int tmp=rc;
    tree[id].rs=tree[tmp].ls;
    tree[tmp].ls=id;
    id=tmp;
    pushup(lc);pushup(id);
}
void rg(int &id)
{
    int tmp=lc;
    tree[id].ls=tree[tmp].rs;
    tree[tmp].rs=id;
    id=tmp;
    pushup(rc);pushup(id);
}
void insert(int &id,int p)
{
    if(!id)
    {
        id=++tot;
        tree[id].val=p;
        tree[id].siz=tree[id].cnt=1;
        tree[id].key=rand();
        return;
    }
    if(tree[id].val==p)
    {
        ++tree[id].cnt;
        pushup(id);
        return;
    }
    if(p>tree[id].val)
    {
        insert(rc,p);
        if(tree[id].key<tree[rc].key)lf(id);
    }
    else
    {
        insert(lc,p);
        if(tree[id].key<tree[lc].key)rg(id);
    } 
    pushup(id);
}
void del(int &id,int p)
{
    if(!id)return;
    if(tree[id].val==p)
    {
        if(tree[id].cnt>1)
        {
            --tree[id].cnt;
            pushup(id);
        }
        else
        {
            if(lc||rc)
            {
                if(rc==0||tree[lc].key>tree[rc].key)
                {
                    rg(id);
                    del(rc,p);
                }
                else
                {
                    lf(id);
                    del(lc,p);
                }
                pushup(id);
            }
            else id=0;
            return;
        }
        return;
    }
    else if(tree[id].val<p)del(rc,p);
    else del(lc,p);
    pushup(id);
}
int getrank(int id,int p)
{
    if(!id)return 1;
    if(tree[id].val==p)return tree[lc].siz+1;
    if(p<tree[id].val)return getrank(lc,p);
    else return getrank(rc,p)+tree[lc].siz+tree[id].cnt;
}
int getnum(int id,int k)
{
    if(id==0)return 0;
    if(tree[lc].siz>=k)return getnum(lc,k);
    else if(tree[lc].siz+tree[id].cnt>=k)return tree[id].val;
    else return getnum(rc,k-(tree[lc].siz+tree[id].cnt));
}
int getpre(int val)
{
    tree[0].val=-1e9;
    int ans=0,p=rt;
    while(p)
    {
        if(val==tree[p].val)
        {
            if(tree[p].ls)
            {
                p=tree[p].ls;
                while(tree[p].rs)p=tree[p].rs;
                ans=p;
            }
            break;
        }
        if(tree[p].val<val&&tree[p].val>tree[ans].val)ans=p;
        p=val<tree[p].val? tree[p].ls : tree[p].rs;
    }
    return tree[ans].val;
}
int getnxt(int val)
{
    tree[0].val=1e9;
    int ans=0,p=rt;
    while(p)
    {
        if(val==tree[p].val)
        {
            if(tree[p].rs)
            {
                p=tree[p].rs;
                while(tree[p].ls)p=tree[p].ls;
                ans=p;
            }
            break;
        }
        if(tree[p].val>val&&tree[p].val<tree[ans].val)ans=p;
        p=val<tree[p].val? tree[p].ls :tree[p].rs; 
    }
    return tree[ans].val;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        int x;
        cin>>x;
        insert(rt,x);
    }
    last=0;
    for(int i=1;i<=m;++i)
    {
        int k,x;
        cin>>k>>x;
        x^=last;
        if(k==1)insert(rt,x);
        else if(k==2)del(rt,x);
        else if(k==3)last=getrank(rt,x),ans^=last;
        else if(k==4)last=getnum(rt,x),ans^=last;
        else if(k==5)last=getpre(x),ans^=last;
        else if(k==6)last=getnxt(x),ans^=last;
    }
    cout<<ans;
    return 0;
}

by 虫洞吞噬者 @ 2022-09-05 22:04:25

已解决，警示后人，最大值的初始值要赋值为INT_MAX