[题解] Luogu P1486 郁闷的出纳员 Treap解法

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

本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可
本文链接:https://acxblog.site/archives/sol_luogu_1486.html