Problem

I 命令 I_k 新建一个工资档案，初始工资为 k。如果某员工的初始工资低于工资下界，他将立刻离开公司。

A 命令 A_k 把每位员工的工资加上 k

S 命令 S_k 把每位员工的工资扣除 k

F 命令 F_k 查询第 k 多的工资

Solution

本题是平衡树的板子题。但由于智商受限，错了很多遍。
本题除了一般 Treap 以外，还有两个难点，一个是对全体修改转变为放置在外面的整体标记，以及对后加入的元素消除标记影响。
另一个则是对 Treap 进行这样一个操作：删除所有 <d 的值。

关于如何删除这个东西，有一个比较合适的做法。
找 d 的前驱（但这个前驱可以等于它），然后总结成如下的算法：

void del(Node *&x, int v) {
    if(!x) return;
    if(x->v == v) {
        x->ch[0]=NULL, updata(x);
    }
    else if(x->v > v) del(x->ch[0], v), updata(x);
    else {
        del(x->ch[1], v);
        x->ch[0]=NULL;
        x=x->ch[1];
    }
}

这个操作比较神奇。真的。
如果走到了前驱，那么往右走不用管，左子树则必须删除。
再往上走，它的路径绝对覆盖所有比前驱结点小的点。
让我们来证明一下：
好，找到前驱节点，往上回溯。如果前驱是这个玩意的右子树，那么它的左子树必须全部删除，只能往上找。
如果前驱是这个玩意的左子树，那么其父亲节点肯定比前驱大。这时这个点的右子树肯定不用管，那么只能再往上找。
这样的话，我们判断的范围从前驱到根节点，由于根节点的判断范围覆盖了整棵树，所以我们能够证明我们这么做能删除掉整棵树的多余节点。因为从前驱到根节点，我们对于每个点的左右子树，要么是从那里上来的，要么是要删掉的，要么是不能动的。这样的话，我们就完整的判断了这棵树的每个极大子树需不需要删除。
听不懂也没关系，因为我讲得太菜了，讲了你们当然听不懂的。
如果找不到前驱，就说明这棵树要整个删除。
然后就这么把问题解决了。

同时这个题还给我们几个教训：

1. 每个点的子树若有改变，updata
2. 每个函数前，判断指针是否为空
3. 每个使用指针的地方，判断指针是否为空

4. 如何用 getchar 来读入字母：

   inline char gu() {
    char ch;
    while(ch=getchar())
        if(isupper(ch)) return ch;
   }

5. 插入时记得旋转

Code

// Code by ajcxsu
// Problem: Luogu P1486
// F**king Treap Problem

#include<bits/stdc++.h>
using namespace std;

template<typename T> void gn(T &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

struct Node {
    int v,f,s,c;
    Node *ch[2];
    Node() {
        v=0, f=rand(), s=c=1;
        ch[0]=ch[1]=NULL;
    }
};
Node *root=NULL;
int delta,cnt;

inline void updata(Node *x) {
    if(!x) return;
    x->s=x->c;
    if(x->ch[0]) x->s+=x->ch[0]->s;
    if(x->ch[1]) x->s+=x->ch[1]->s;
}

inline void rot(Node *&x, bool type) {
    Node *t=x->ch[type];
    x->ch[type]=t->ch[!type];
    t->ch[!type]=x;
    updata(x);
    updata(t);
    x=t;
}

void ins(Node *&x, int v) {
    if(x==NULL) {
        x=new Node;
        x->v=v;
        return;
    }
    if(x->v==v) x->c++, updata(x);
    else {
        bool dl=v > x->v;
        ins(x->ch[dl], v);
        if(x->ch[dl]->f > x->f) rot(x, dl);
        else updata(x);
    }
}

void aft(Node *x, int v, int &ans) {
    if(!x) return;
    // printf("????\n");
    if(x->v < v) aft(x->ch[1], v, ans);
    else {
        // printf("???\n");
        ans=min(ans,x->v);
        aft(x->ch[0], v, ans);
    }
}

void del(Node *&x, int v) {
    if(!x) return;
    if(x->v == v) {
        x->ch[0]=NULL, updata(x);
    }
    else if(x->v > v) del(x->ch[0], v), updata(x);
    else {
        del(x->ch[1], v);
        x->ch[0]=NULL;
        x=x->ch[1];
    }
}

Node* kth(Node *x,int k) {
    if(!x || k<=0 || k>x->s) return NULL;
    int ss=0;
    if(x->ch[0]) ss=x->ch[0]->s;
    if(k>=ss+1 && k<=ss+x->c) return x;
    else if(k>ss+x->c) return kth(x->ch[1], k-ss-x->c);
    else return kth(x->ch[0], k);
}

inline char gu() {
    char ch;
    while(ch=getchar())
        if(isupper(ch)) return ch;
}

int main() {
    srand(time(NULL));
    int n,b;
    gn(n), gn(b);
    char con;
    int v;
    while(n--) {
        con=gu();
        gn(v);
        if(con=='I') { if(v>=b) ins(root,v-delta),cnt++;}
        else if(con=='A') delta+=v;
        else if(con=='S') {
            delta-=v;
            // printf(" %d\n",b-delta);
            int aim=0x7fffffff; aft(root,b-delta,aim);
            // printf(" %d\n",aim);
            if(aim!=0x7fffffff) del(root,aim);
            else root=NULL;
        }
        else if(con=='F') {
            if(!root || v>root->s) printf("-1\n");
            else {
                Node *d=kth(root,root->s-v+1);
                // if(!d) printf("-1\n");
                printf("%d\n",d->v+delta);
            }
        }
    }
    if(!root) printf("%d\n",cnt);
    else printf("%d\n",cnt-root->s);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol_luogu_1486.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆