FHQtreap TLE+RE求助

CHNZhang @ 2022-10-21 19:13:33

by CHNZhang @ 2022-10-21 19:28:10

#include<bits/stdc++.h>
#define rint register int
#define LL long long int
#define MX 2100005
using namespace std;
inline int read()
{
    int x = 0, ff = 1; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') ff = -ff; s = getchar(); }
    while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
    return x * ff;
}
int n,m;
int ls[MX],rs[MX],val[MX],key[MX],sz[MX],tot;
inline int newnode(int w)
{
    tot++;
    ls[tot]=rs[tot]=0;val[tot]=w;sz[tot]=1;
    key[tot]=rand();
    return tot;
}
inline int pushup(int x)
{
    sz[x]=sz[ls[x]]+sz[rs[x]]+1;
}
void split(int p,int w,int &x,int &y)
{
    if(p==0)
    {
        x=y=0;
        return ;
    }
    if(val[p]<=w)
    {
        x=p;
        split(rs[p],w,rs[p],y);
    }
    else
    {
        y=p;
        split(ls[p],w,x,ls[p]);
    }
    pushup(p);
}
int combine(int x,int y)
{
    if(x==0||y==0)
        return x+y;
    if(key[x]<key[y])
    {
        rs[x]=combine(rs[x],y);
        pushup(x);
        return x;
    }
    else
    {
        ls[y]=combine(x,ls[y]);
        pushup(y);
        return y;
    }
}
inline void insert(int w,int &rt)
{
    int tmp1=0;
    split(rt,w,tmp1,rt);
    tmp1=combine(tmp1,newnode(w));
    rt=combine(tmp1,rt);
}
inline int getrank(int x,int &rt)
{
    int res=0,tmp1=0;
    split(rt,x-1,tmp1,rt);
    res=sz[tmp1];
    rt=combine(tmp1,rt);
    return res+1;
}
inline int getval(int x,int rt)
{
    //cout<<x<<endl;
    if(sz[ls[rt]]==x-1)return val[rt];
    if(sz[ls[rt]]>=x)return getval(x,ls[rt]);
    return getval(x-sz[ls[rt]]-1,rs[rt]);
}
inline void del(int w,int &rt)
{
    int tmp1=0,tmp2=0;
    split(rt,w,tmp1,rt);
    split(tmp1,w-1,tmp1,tmp2);
    tmp2=combine(ls[tmp2],rs[tmp2]);
    tmp1=combine(tmp1,tmp2);
    rt=combine(tmp1,rt);
}
inline int getpre(int x,int &rt)
{
    int res=0,tmp=0;
    split(rt,x-1,tmp,rt);
    res=getval(sz[tmp],tmp);
    rt=combine(tmp,rt);
    return res;
}
inline int getnxt(int x,int &rt)
{
    int res=0,tmp=0;
    split(rt,x,rt,tmp);
    res=getval(1,tmp);
    rt=combine(rt,tmp);
    return res;
}
int main()
{
    //freopen("P6136_1.in","r",stdin);
    srand(time(0));
    rint i,rt=0,lst=0,opt,x,ans=0;
    n=read();m=read();
    for(i=1;i<=n;i++)
    {
        x=read();
        insert(x,rt);
    }
    //cout<<tot<<endl;
    for(i=1;i<=m;i++)
    {
        opt=read();x=read();
        x^=lst;
        if(opt==1)
            insert(x,rt);
        else if(opt==2)
            del(x,rt);
        else if(opt==3)
        {
            lst=getrank(x,rt);
            ans^=lst;
        }
        else if(opt==4)
        {
            lst=getval(x,rt);
            ans^=lst;
        }
        else if(opt==5)
        {
            lst=getpre(x,rt);
            ans^=lst;
        }
        else if(opt==6)
        {
            lst=getnxt(x,rt);
            ans^=lst;
        }
    }
    cout<<ans<<endl;
    return 0;
}

by LgxTpre @ 2022-10-21 19:36:17

@CHNZhang 两个问题

1. 数组还是开小了，它可能全是插入操作
2. 您的 pushup 打成 int 类型了，应该是 void，没有返回值所以TLE

by _Imaginary_ @ 2022-10-21 19:37:02

@CHNZhang 如果下载的数据本地跑没问题，有可能是数组越界等导致的UB。

by CHNZhang @ 2022-10-21 19:38:57

@LgxTpre 感谢，问题解决了，太粗心了...

by CHNZhang @ 2022-10-21 19:40:07

@Imaginary 感谢