JDOJ-1855: [NOI2004]郁闷的出纳员

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;
}

蒟蒻：啊啊啊啊啊啊啊啊！！！哭死