Violet___Evergarden @ 2022-08-17 15:43:52
TLE了3个点请问哪里写假了
#include <iostream>
using namespace std;
const int kMaxN=1e6+1e5+1;
int read()
{
int num(0);char in=getchar();
while(in<'0'||in>'9')in=getchar();
while(in>='0'&&in<='9'){num=(num<<1)+(num<<3)+(in^48);in=getchar();}
return num;
}
struct SPLAY
{
int son[2];
int num,cnt,size,father;
}tr[kMaxN];
int n,m,root,point,last,ans;
void Clear(int where)
{
tr[where].father=tr[where].son[0]=tr[where].son[1]=tr[where].num=tr[where].cnt=tr[where].size=0;
}
void Count(int where)
{
tr[where].size=tr[tr[where].son[0]].size+tr[tr[where].son[1]].size+tr[where].cnt;
}
void Turn(int where)
{
int fa=tr[where].father,fafa=tr[fa].father,derection=(tr[fa].son[1]==where);
tr[fa].son[derection]=tr[where].son[derection^1];
tr[tr[where].son[derection^1]].father=fa;
tr[where].son[derection^1]=fa;
tr[fa].father=where;
tr[where].father=fafa;
if(fafa)
{
tr[fafa].son[tr[fafa].son[1]==fa]=where;
}
Count(fa);
Count(where);
Count(fafa);
}
void Splay(int x)
{
while(tr[x].father)
{
int fa=tr[x].father,fafa=tr[fa].father;
if(fafa)
{
if((tr[fa].son[0]==x&&tr[fafa].son[0]==fa)||(tr[fa].son[1]==x&&tr[fafa].son[1]==fa))
{
Turn(fa);
}
else
{
Turn(x);
}
}
Turn(x);
}
root=x;
}
void Insert(int x)
{
if(!root)
{
root=++point;
tr[root].num=x;
tr[root].cnt=1;
tr[root].size=1;
return;
}
int now=root,fa=0;
while(1)
{
if(!now)
{
tr[++point].num=x;
tr[point].cnt=1;
tr[point].size=1;
tr[point].father=fa;
tr[fa].son[x>tr[fa].num]=point;
Count(fa);
Splay(point);
return;
}
if(tr[now].num==x)
{
tr[now].cnt++;
Count(now);
Count(fa);
Splay(now);
return;
}
fa=now;
now=tr[now].son[x>tr[now].num];
}
}
int Find(int x)
{
int now=root;
while(now)
{
if(tr[now].num==x)return now;
now=tr[now].son[x>tr[now].num];
}
}
int Getqq()
{
int now=tr[root].son[0];
while(tr[now].son[1])now=tr[now].son[1];
return now;
}
int Gethj()
{
int now=tr[root].son[1];
while(tr[now].son[0])now=tr[now].son[0];
return now;
}
void Delete(int x)
{
int now=Find(x);
Splay(now);
if(tr[root].cnt>=2)
{
tr[root].cnt--;
tr[root].size--;
return;
}
if(!tr[root].son[0]&&!tr[root].son[1])
{
Clear(root);
root=0;
return;
}
else if(!tr[root].son[0])
{
int lastr=root;
root=tr[root].son[1];
tr[root].father=0;
Clear(lastr);
}
else if(!tr[root].son[1])
{
int lastr=root;
root=tr[root].son[0];
tr[root].father=0;
Clear(lastr);
}
else
{
int lastr=root,qq=Getqq();
Splay(qq);
tr[root].son[1]=tr[lastr].son[1];
tr[tr[lastr].son[1]].father=root;
Clear(lastr);
Count(root);
}
}
int GetNum(int x)
{
int now=root;
while(1)
{
if(x<=tr[tr[now].son[0]].size)
{
now=tr[now].son[0];
}
else
{
x-=tr[tr[now].son[0]].size+tr[now].cnt;
if(x<=0)return tr[now].num;
now=tr[now].son[1];
}
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
{
Insert(read());
}
while(m--)
{
int order(read()),x(read());
x^=last;
if(order==1)Insert(x);
else if(order==2)Delete(x);
else if(order==3)
{
Insert(x);
last=tr[tr[root].son[0]].size+1;
ans^=last;
Delete(x);
}
else if(order==4)
{
last=GetNum(x);
ans^=last;
}
else if(order==5)
{
Insert(x);
last=tr[Getqq()].num;
ans^=last;
Delete(x);
}
else
{
Insert(x);
last=tr[Gethj()].num;
ans^=last;
Delete(x);
}
}
cout<<ans;
return 0;
}
by Violet___Evergarden @ 2022-08-17 15:51:54
在每次操作找到答案之后把节点splay就过了?
by Violet___Evergarden @ 2022-08-17 15:52:24
啊我一直以为只需要在插入和删除的时候splay
by GoldenFishX @ 2022-08-17 15:54:21
%%%