BZOJ1503——郁闷的出纳员

1、题目大意：一道treap题，支持插入，询问第K大，还有全体修改+上一个值，如果某个点值小于x，那么就删除这个点

插入100000次，询问100000次，修改100次。。最后输出删了多少个点

2、分析：首先看修改是100次的，我就没有多想什么lazy，什么的

就是名次树，修改的话，我们就遍历treap，全部修改我们就O(n)搞一下

最后说一个坑爹的地方，就是插入前就否认的点不算T_T

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node{
    Node* ch[2];
    int r, v, s, c;
    inline bool operator < (const Node& rhs) const{
        return r < rhs.r;
    }
    inline int cmp(int x){
        if(x == v) return -1;
        if(x < v) return 0;
        return 1;
    }
    inline void maintain(){
        s = c;
        if(ch[0] != NULL) s += ch[0] -> s;
        if(ch[1] != NULL) s += ch[1] -> s;
        return;
    }
};
Node ft[500000];
struct treap{

    Node *p;
    int cnt;
    inline void init(){
        cnt = -1;
        p = NULL;
        return;
    }
    inline void rotate(Node* &o, int d){
        Node *k = o -> ch[d ^ 1];
        o -> ch[d ^ 1] = k -> ch[d];
        k -> ch[d] = o;
        o -> maintain();
        k -> maintain();
        o = k;
        return;
    }
    inline void insert(Node* &o, int x){
        if(o == NULL){
            o = &ft[++ cnt];
            o -> ch[0] = o -> ch[1] = NULL;
            o -> v = x;
            o -> r = rand();
            o -> c = 1;
        }
        else if(o -> v == x) o -> c ++;
        else{
            int d = o -> cmp(x);
            insert(o -> ch[d], x);
            if(o -> ch[d] -> r > o -> r) rotate(o, d ^ 1);
        }
        o -> maintain();
        return;
    }
    inline void A(Node* &o, int x){
        if(o == NULL) return;
        o -> v += x;
        A(o -> ch[0], x);
        A(o -> ch[1], x);
        return;
    }
    inline void S(Node* &o, int x){
        while(o != NULL && o -> v < x) o = o -> ch[1];
        if(o == NULL) return;
        if(o -> ch[0] != NULL) S(o -> ch[0], x);
        if(o -> ch[1] != NULL) S(o -> ch[1], x);
        if(o != NULL) o -> maintain();
        return;
    }
    inline int k_th(Node* &o, int k){
        int ls = 0, rs = 0;
        if(o -> ch[0] != NULL) ls = o -> ch[0] -> s;
        if(ls >= k) return k_th(o -> ch[0], k);
        else if(ls + o -> c >= k) return o -> v;
        else return k_th(o -> ch[1], k - ls - o -> c);
    }
} wt;
int main(){
    int n, m, orz = 0;
    scanf("%d%d", &n, &m);
    wt.init();
    for(int i = 1; i <= n; i ++){
        char str[5]; int k;
        scanf("%s%d", str, &k);
        if(str[0] == 'I'){
            if(k >= m){
                orz ++;
                wt.insert(wt.p, k);
            }
        }
        else if(str[0] == 'A') wt.A(wt.p, k);
        else if(str[0] == 'F'){
            if(wt.p == NULL || k > wt.p -> s) printf("-1\n");
            else printf("%d\n", wt.k_th(wt.p, wt.p -> s - k + 1));
        }
        else {
            wt.A(wt.p, -k);
            wt.S(wt.p, m);
        }
    }
    printf("%d\n", orz - wt.p -> s);
    return 0;
}

巴特西

BZOJ1503——郁闷的出纳员

最新文章

热门文章