嘉年华 @ 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;就可以了