本地卡死,提交AC

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

嘉年华 @ 2021-10-20 16:21:02

没有开fread

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
//#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?EOF:*S++)
namespace get_out
{
    char B[1<<15],*S=B,*T=B;
    char op;
    inline void read_(int &x)
    {
        x=0;
        int fi(1);
        op=getchar();
        while((op<'0'||op>'9')&&op!='-') op=getchar();
        if(op=='-') op=getchar(),fi=-1;
        while(op>='0'&&op<='9') x=(x<<1)+(x<<3)+(op^48),op=getchar();
        x*=fi;
        return;
    }
    inline void read_(long long &x)
    {
        x=0;
        int fi(1);
        op=getchar();
        while((op<'0'||op>'9')&&op!='-') op=getchar();
        if(op=='-') op=getchar(),fi=-1;
        while(op>='0'&&op<='9') x=(x<<1)+(x<<3)+(op^48),op=getchar();
        x*=fi;
        return;
    }
    inline void read_(double &x)
    {
        x=0.0;
        float fi(1.0),sm(0.0);
        op=getchar();
        while((op<'0'||op>'9')&&op!='-') op=getchar();
        if(op=='-') op=getchar(),fi=-1.0;
        while(op>='0'&&op<='9') x=(x*10.0)+(op^48),op=getchar();
        if(op=='.') op=getchar();
        while(op>='0'&&op<='9') sm=(sm*10.0)+(op^48),op=getchar();
        while(sm>1.0) sm/=10.0;
        x+=sm,x*=fi;
        return;
    }
    inline void postive_write(int x)
    {
        if(x>9) postive_write(x/10);
        putchar(x%10|'0');
    }
    inline void postive_write(long long x)
    {
        if(x>9) postive_write(x/10);
        putchar(x%10|'0');
    }
    inline void write_(int x)
    {
        if(x<0) x=-x,putchar('-');
        postive_write(x);
    }
    inline void write_(int x,char ch)
    {
        write_(x),putchar(ch);
    }
    inline void write_(long long x)
    {
        if(x<0) x=-x,putchar('-');
        postive_write(x);
    }
    inline void write_(long long x,char ch)
    {
        write_(x),putchar(ch);
    }
}
using get_out::read_;
#define maxn 100005

template<int N=1,typename _Tp=int,_Tp INF=2147483647> class Splay
{
    private:
        int Root,node_cnt;
        struct Node
        {
            _Tp v;
            int cnt,siz,fa,ch[2];
            Node(){}
        };
        vector<Node> node;
        vector<int> del_list;
        int vir_alloc()
        {
            if(!del_list.empty())
            {
                int tmp=del_list.back();
                del_list.pop_back();
                return tmp;
            }
            ++node_cnt;
            if(node_cnt>=node.size()) node.emplace_back(Node());
            return node_cnt;
        }
        void update(int x)
        {
            node[x].siz=node[node[x].ch[0]].siz+node[node[x].ch[1]].siz+node[x].cnt;
        }
        void rotate(int x)
        {
            int y=node[x].fa,z=node[y].fa,k=(node[y].ch[1]==x);
            node[z].ch[node[z].ch[1]==y]=x;
            node[x].fa=z;
            node[y].ch[k]=node[x].ch[k^1];
            node[node[x].ch[k^1]].fa=y;
            node[x].ch[k^1]=y;
            node[y].fa=x;
            update(y),update(x);
        }
        void splay(int x,int target)
        {
            while(node[x].fa!=target)
            {
                int y=node[x].fa,z=node[y].fa;
                if(z!=target)
                    ((node[z].ch[0]==y)^(node[y].ch[0]==x))?rotate(x):rotate(y);
                rotate(x);
            }
            if(!target)Root=x;
        }
        void find(_Tp x)
        {
            int cur=Root;
            if(!cur)return;
            while(node[cur].ch[x>node[cur].v]&&x!=node[cur].v)
                cur=node[cur].ch[x>node[cur].v];
            splay(cur,0);
        }
    public:
        Splay(){Root=node_cnt=0;node.resize(N);insert(INF),insert(-INF);}//初始化
        void insert(_Tp x)
        {
            int cur=Root,from=0;
            while(cur&&x!=node[cur].v)
                from=cur,cur=node[cur].ch[x>node[cur].v];
            if(cur)
                ++node[cur].cnt;
            else
            {
//              cur=++node_cnt;
                cur=vir_alloc();
                if(!from) Root=cur;
                else node[from].ch[x>node[from].v]=cur;
                node[cur].v=x;
                node[cur].cnt=1;
                node[cur].fa=from;
                node[cur].siz=1;
                node[cur].ch[0]=node[cur].ch[1]=0;
            }
            splay(cur,0);
        }
        int find_pre_id(_Tp x)
        {
            find(x);
            if(node[Root].v<x)return Root;
            int cur=node[Root].ch[0];
            while(node[cur].ch[1]) cur=node[cur].ch[1];
            return cur;
        }
        int find_nxt_id(_Tp x)
        {
            find(x);
            if(node[Root].v>x)return Root;
            int cur=node[Root].ch[1];
            while(node[cur].ch[0]) cur=node[cur].ch[0];
            return cur;
        }
        _Tp find_pre(_Tp x)
        {
            x=find_pre_id(x);
            return node[x].v;
        }
        _Tp find_nxt(_Tp x)
        {
            x=find_nxt_id(x);
            return node[x].v;
        }
        void erase(_Tp x)
        {
            int x_pre=find_pre_id(x),x_nxt=find_nxt_id(x);
            splay(x_pre,0);
            splay(x_nxt,x_pre);
            int cur=node[x_nxt].ch[0];
            if(node[cur].cnt>1)
            {
                --node[cur].cnt;
                splay(cur,0);
            }
            else del_list.emplace_back(node[x_nxt].ch[0]),node[x_nxt].ch[0]=0;
        }
        _Tp kth(int rank)
        {
            ++rank;
            int cur=Root,son;
            if(node[cur].siz<rank) return INF;
            while(1)
            {
                son=node[cur].ch[0];
                if(rank>node[son].siz+node[cur].cnt)
                {
                    rank-=node[son].siz+node[cur].cnt;
                    cur=node[cur].ch[1];
                }
                else if(node[son].siz>=rank) cur=son;
                else return node[cur].v;
            }
        }
        int get_rank(_Tp x)
        {
            find(x);
            return node[node[Root].ch[0]].siz;
        }
};
Splay<> S;
int n,m;
int ans,la;

signed main()
{
    read_(n),read_(m);
    for(int i=0,x;i<n;++i) read_(x),S.insert(x);
    for(int i=0,op,x;i<m;++i)
    {
        read_(op);
        read_(x);
        x=x^la;
        switch(op)
        {
            case 1:S.insert(x);break;
            case 2:S.erase(x);break;
            case 3:S.insert(x),ans^=(la=S.get_rank(x)),S.erase(x);break;
            case 4:ans^=(la=S.kth(x));break;
            case 5:ans^=(la=S.find_pre(x));break;
            case 6:ans^=(la=S.find_nxt(x));break;
        }
    }
    cout<<ans<<'\n';

    return 0;
}

提交记录:
https://www.luogu.com.cn/record/60400653
本地运行样例到"4 1"那一行就卡死了,但提交之后就AC了


by 嘉年华 @ 2021-10-20 16:51:02

找到错误了,本地resize出来是随机数,luogu给你的是全0的内存,在初始化时加上node[0].siz=0;就可以了


|