求助,序列操作的问题

回复帖子

@islandl  2021-07-22 18:10 回复

请问,S 操作中,为什么把l转到根,r转到l下,取r的左儿子就错了,应该是一样的啊

谢谢各位大佬

代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,m;
const int N=100010;
struct node
{
    int p,v,s[2],size;
    void init(int _v,int _p)
    {
        v=_v;p=_p;size=1;
    }
}tr[N];
int root=0,num=0;
void pushup(int x)
{
  tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+1;
}
void rotate(int x)
{
   int y=tr[x].p,z=tr[y].p;
   int k= tr[y].s[1]==x;
   tr[z].s[tr[z].s[1]==y]=x; tr[x].p=z;
   tr[y].s[k]=tr[x].s[k^1];  tr[tr[x].s[k^1]].p=y;
   tr[x].s[k^1]=y; tr[y].p=x;
   pushup(y);pushup(x);
}
void splay(int x,int k)
{
  while(tr[x].p!=k)
  {
    int y=tr[x].p,z=tr[y].p;
    if(z!=k)
    {
       if((tr[z].s[1]==y)^(tr[y].s[1]==x)) rotate(x);
       else rotate(y);
    }
    rotate(x);
  }
  if(k==0) root=x;
}
int insert(int v)
{
  int u=root,p=0;
  while(u)
  {
    p=u;
    u=tr[u].s[v>tr[u].v];
  }
  u=++num;
  if(p) tr[p].s[v>tr[p].v]=u;
  tr[u].init(v,p);
  splay(u,0);
  return u;
}//insert直接返回哨兵位置 
int get_k(int x)
{
    int u=root;
    while(true)
    {
        if(x<=tr[tr[u].s[0]].size) u=tr[u].s[0];
        else if(x==tr[tr[u].s[0]].size+1) return tr[u].v;
        else x=x-tr[tr[u].s[0]].size-1,u=tr[u].s[1];
    }
}
int find(int x)
{
    int u=root,ans;
    while(u)
    {
        if(tr[u].v>=x) ans=u,u=tr[u].s[0];
        else u=tr[u].s[1];
    }    
    cout<<tr[ans].v<<endl;
    return ans;
}//找到高于工资下限的第一个数,即r+1 
int main()
{
    int n,min;
    int r=insert(2147483647);
    int l=insert(-2147483647);//哨兵 
    scanf("%d%d",&n,&min);
    int x,delta=0,ans=0,num=0;
    //delta为工资改变量,splay存原工资,存时-delta,判断时+delta 
    char op[3];
    for(int i=1;i<=n;i++)
    {
        scanf("%s",op);
        scanf("%d",&x);
        if(op[0]=='I')
        {
            if(x>=min) 
            {
                insert(x-delta);//把所有员工看作同时加入,把x看作改变后的量,新插入-delta, 
                num++;
            }
        }
        else if(op[0]=='A') delta+=x;
        else if(op[0]=='S')
        {
            delta-=x;
            r=find(min-delta);//x+delta<min 所以x<min-delta离开 
            splay(r,0);splay(l,r);
            tr[l].s[1]=0;//删去低于工资下限的 
            pushup(l);pushup(r);//size改变,更新 
        }
        else 
        {
            if(tr[root].size-2<x) printf("-1\n");
            else printf("%d\n",get_k(tr[root].size-x)+delta);//splay中存的是原工资,+delta 
        }
    }
    printf("%d",num-tr[root].size+2);//两边哨兵加回来 
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。