萌新刚学OI,求帮忙调代码

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

_lzh_ @ 2021-02-24 17:00:25

写的Treap,只有20pts,求大佬帮忙看看

#include<bits/stdc++.h>
#define N 1100000
#define r root
#define int long long
using namespace std;
const int maxx=1e9+1;
int root=0,sum=0,m,mm;
int v[N],s[N],n[N],rd[N],ls[N],rs[N];
void more_new(int x)
{
    s[x]=s[ls[x]]+s[rs[x]]+n[x];
}
void turn_left(int &x)
{
    int a;
    a=rs[x];
    rs[x]=ls[a];
    ls[a]=x;
    more_new(x),more_new(a);
    x=a;
}
void turn_right(int &x)
{
    int a;
    a=ls[x];
    ls[x]=rs[a];
    rs[a]=x;
    more_new(x),more_new(a);
    x=a;
}
void in(int &x,int f)
{
    if(x==0)
    {
        x=++sum;
        s[x]=n[x]=1;
        v[x]=f;
        rd[x]=rand();
        return;
    }
    if(v[x]==f)
    {
        n[x]+=1;
        s[x]+=1;
        return;
    }
    if(f>v[x])
        in(rs[x],f);
    else
        in(ls[x],f);
    if(f>v[x])
    {
        if(rd[x]<rd[rs[x]])
            turn_left(x);
    }
    else
    {
        if(rd[x]<rd[ls[x]])
            turn_right(x);
    }
    more_new(x);
}
void out(int &x,int f)
{
    if(x==0)return;
    if(f<v[x])
    {
        out(ls[x],f);
    }
    else if(f>v[x])
    {
        out(rs[x],f);
    }
    else if(f==v[x])
    {
        if(ls[x]==0&&rs[x]==0)
        {
            n[x]-=1,s[x]-=1;
            if(n[x]==0)x=0;
        }
        else if(ls[x]==0&&rs[x]!=0)
        {
            turn_left(x);
            out(ls[x],f);
        }
        else if(ls[x]!=0&&rs[x]==0)
        {
            turn_right(x);
            out(rs[x],f);
        }
        else
        {
            if(rd[ls[x]]>rd[rs[x]])
            {
                turn_right(x);
                out(rs[x],f);
            }
            else
            {
                turn_left(x);
                out(ls[x],f);
            }
        }
    }
    more_new(x);
}
int rankk(int x,int f)
{
    if(x==0)return 0;
    if(v[x]==f)
        return s[ls[x]]+1;
    if(v[x]<f)
        return s[ls[x]]+n[x]+rankk(rs[x],f);
    if(v[x]>f)
        return rankk(ls[x],f);
    return 0;
}
int name(int x,int f)
{
    if(x==0)return 0;
    if(s[ls[x]]>=f)
        return name(ls[x],f);
    else if(s[ls[x]]+n[x]<f)
        return name(rs[x],f-n[x]-s[ls[x]]);
    else
        return v[x];
}
int before(int x,int f)
{
    if(x==0)
        return -maxx;
    if(v[x]>=f)
        return before(ls[x],f);
    else
        return max(v[x],before(rs[x],f));
}
int after(int x,int f)
{
    if(x==0)
        return maxx;
    if(v[x]<=f)
        return after(rs[x],f);
    else
        return min(v[x],after(ls[x],f));
}
int ans=0,ltt=0;
signed main()
{
//  freopen("test.txt","w",stdout);
    cin>>m>>mm;
    for(int i=1;i<=m;i++)
    {
        int xxx;
        cin>>xxx;
        in(r,xxx);
    }
    for(int i=1;i<=mm;i++)
    {
        int opt,x;
        cin>>opt>>x;
        x^=ltt;
        if(opt==1)
            in(root,x);
        if(opt==2)
            out(root,x);
        if(opt==3)
            ltt=rankk(root,x)+1,ans^=ltt;
        if(opt==4)
            ltt=name(root,x),ans^=ltt;
        if(opt==5)
            ltt=before(root,x),ans^=ltt;
        if(opt==6)
            ltt=after(root,x),ans^=ltt;
//        cout<<opt<<" "<<x<<endl;
    }
    cout<<ans;
    return 0;
}

by dying @ 2021-02-24 21:22:34

又来了,刚学OI的treap


by peterwuyihong @ 2021-02-24 21:48:17

@lzh

$2,$输出了负数,很奇怪,对症下药

by _lzh_ @ 2021-02-24 21:51:24

@peterwuyihong 谢谢巨佬,我去改改


|