为什么会RE???

P6136 【模板】普通平衡树(数据加强版)

刘子瑞 @ 2020-08-25 17:49:33

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<ctime>
using namespace std;
const int MAXN=2e6+10;
int M,N,tot,root;
struct TREE
{
    int key,ra,lson,rson,size;
}tree[MAXN];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int newpoint(int x)
{
    tot++;
    tree[tot].key=x;
    tree[tot].ra=rand();
    tree[tot].size=1;
}
void update(int a)
{
    tree[a].size=1 + (tree[tree[a].lson].size + tree[tree[a].rson].size);
    return ;
}
void split(int a,int num,int &l,int &r)
{
    if( !a ) 
    {
        l=r=0;
        return ;
    }
    if(tree[a].key <= num )
    {
        l=a;
        split(tree[a].rson,num,tree[a].rson,r);
    }
    else 
    {
        r=a;
        split(tree[a].lson,num,l,tree[a].lson);
    }
    update(a);
    return ;
}
int merge(int d1,int d2)
{
    if( !d1 || !d2 ) return d1+d2;
    if( tree[d1].ra < tree[d2].ra )
    {
        tree[d2].lson=merge(d1,tree[d2].lson);
        update(d2);
        return d2;
    }
    else 
    {
        tree[d1].rson=merge(tree[d1].rson,d2);
        update(d1);
        return d1;
    }
}
void insert(int x)
{
    newpoint(x);
    int l=0,r=0;
    split(root,x-1,l,r);
    l=merge(l,tot);
    root=merge(l,r);
    return ;
}
void delet(int x)
{
    int l=0,r=0,del=0;
    split(root,x,l,r);
    split(l,x-1,l,del);
    del=merge(tree[del].lson,tree[del].rson);
    l=merge(l,del);
    root=merge(l,r);
    return ;
}
int Queryrank(int x)
{
    int l=0,r=0;
    split(root,x-1,l,r);
    int ans=tree[l].size+1;
    root=merge(l,r);
    return ans;
}
int Querynum(int rankx)
{
    int a=root;
    while(a)
    {
        if( tree[a].size == 1 ) return tree[a].key ;
        if( tree[tree[a].lson].size >= rankx ) a=tree[a].lson;
        else 
        {
            rankx-=tree[tree[a].lson].size;
            if(rankx==1) return tree[a].key;
            rankx--;
            a=tree[a].rson; 
        }
    }

}
int Querypre(int x)
{
    int l=0,r=0;
    split(root,x-1,l,r);
    int pos=l;
    while( tree[pos].rson ) pos=tree[pos].rson;
    root=merge(l,r);
    return tree[pos].key;
}
int Queryneg(int x)
{
    int l=0,r=0;
    split(root,x,l,r);
    int pos=r;
    while( tree[pos].lson ) pos=tree[pos].lson;
    root=merge(l,r);
    return tree[pos].key;
}
int main()
{
    //freopen("P6136_1.in","r",stdin);
    srand(time(0));
    //scanf("%d%d",&N,&M);
    N=read();M=read();
    for(int i=1;i<=N;i++)
    {
        int shu;
        //scanf("%d",&shu);
        shu=read();
        insert(shu);
    }
    int ANS=0,LAST=0;
    for(int item=1;item<=M;item++)
    {
        int cmd,shu;
        //scanf("%d%d",&cmd,&shu);
        cmd=read();shu=read();
        shu=shu^LAST;
        if(cmd==1) insert(shu); 
        else if(cmd==2) delet(shu);
        else if(cmd==3) LAST=Queryrank(shu),ANS^=LAST;
        else if(cmd==4) LAST=Querynum(shu),ANS^=LAST;
        else if(cmd==5) LAST=Querypre(shu),ANS^=LAST;
        else if(cmd==6) LAST=Queryneg(shu),ANS^=LAST;
    }   
    printf("%d\n",ANS); 
    return 0;
}

求dalao查错


by lemir3 @ 2020-08-25 18:06:51

orz lzr


by Social_Zhao @ 2020-08-25 18:16:58

orz lzr


|