[文章目录]
Description
| 名称 | 格式 | 作用 |
| I命令 | I_k | 新建一个工资档案，初始工资为k。如果某员工的初始工资低于工资下界，他将立刻离开公司。 |
| A命令 | A_k | 把每位员工的工资加上k |
| S命令 | S_k | 把每位员工的工资扣除k |
| F命令 | F_k | 查询第k多的工资 |
简单的一个splay，不过好像引起了很多对数据结构的漏洞。尽管，实际上就是一个单点插入，单点查询，区间删除，但是蒟蒻表示呵呵。
首先，第一遍写的时候TLE了，原因是脑袋里装了个二分，每次二分位置，随后插入，然后每次找到个节点并未有将其splay，导致树退化QAQ。splay常数大，还多了个log。
所以我们直接上树上找点，由于是中序遍历，所以logn就找到位置了。然后记得维护树的结构，将其splay到根，双旋的过程中直接就pushup更新了路径上的节点。
删除的话，直接上树里搜，递归删除，代码写得很清真。
单点查询就顺便维护树的结构，将其旋转到根。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,mi,R,ans,now,val,fna;
char st[20];
struct node
{
node *fa,*c[2];
int val,size;
node(int x);
void pushup() {size=c[0]->size+c[1]->size+1;}
}*null=new node(0),*root=null;
node :: node(int x)
{
fa=c[0]=c[1]=null;
val=x;
size=null? 1:0;
}
void rotate(node *x)
{
node *y=x->fa;int l=(x==y->c[1]),r=l^1;
y->c[l]=x->c[r];x->c[r]->fa=y;
x->c[r]=y;x->fa=y->fa;
if(y==y->fa->c[l]) y->fa->c[l]=x;
else y->fa->c[r]=x;
y->fa=x;y->pushup();x->pushup();
if(y==root) root=x;
}
void splay(node *x,node *tar)
{
while(x!=tar)
{
node *y=x->fa,*z=y->fa;
if(y==tar) break;
if(z==tar) {rotate(x);break;}
if((x==y->c[0])^(y==z->c[0])==0) rotate(y);
else rotate(x); rotate(x);
}
}
void Insert(node *&x,int val,node *z)// & 直接就更新了fa的c[]指针
{
if(x==null)
{
x=new node(val);
x->fa=z;
splay(x,null);
return ;
}
if(x->val>val) Insert(x->c[0],val,x);
else Insert(x->c[1],val,x);
}
void del(node *&x)// & 直接就更新了fa的c[]指针
{
while(1)
{
if(x==null) return ;
if(x->c[0]) del(x->c[0]);
if(x->val+now<mi)
{
fna++;
x->c[1]->fa=x->fa;
x=x->c[1];
}
else break;
}
if(x!=null) x->pushup();
}
void find(node *x,int y,node *z)
{
while(1)
{
if(y<=x->c[1]->size) x=x->c[1];
else
{
y-=x->c[1]->size;
if(y==1) break;
y--;x=x->c[0];
}
}
splay(x,z);
}
int main()
{
scanf("%d%d",&n,&mi);
while(n--)
{
scanf("%s%d",st,&val);
switch(st[0])
{
case 'I':
{
if(val>=mi) Insert(root,val-now,null);
break;
}
case 'A':now+=val;break;
case 'S':
{
now-=val;del(root);
break;
}
case 'F':
{
if(val>root->size) puts("-1");
else find(root,val,null),printf("%d\n",root->val+now);
break;
}
}
}
printf("%d",fna);
return 0;
}蒟蒻：啊啊啊啊啊啊啊啊！！！哭死