splay 88分求助

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

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

%%%


|