题解：P1486 [NOI2004] 郁闷的出纳员

XGTD · 2025-04-17 21:41:01 · 题解

Preface

看了一圈，大佬们各显神通，pb_ds，treap，splay，我都不会，献上一个树状数组做法。

Problem statement

维护数据结构，实现单点插入，全局加，全局减，全局第 k 小，同时如果减完后有点小于一个给定的限制就删除。

Solution

首先对于全局加减考虑不加每个点的值，而只是调整这个限制的值，同时记录目前调整的总量插入新点时减去，输出时加上就行了

现在实现插入，删除和全局第 k 小就可以用树状数组上二分解决了，具体可以看 oiwiki fenwick tree。

/*

*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
int c[3000005], rang = 3000005;
void add(int x, int y){
    for(int i = x; i <= rang; i += i & -i){
        c[i] += y;
    }
}
int get(int x){
    int anst = 0;
    for(int i = x; i > 0; i -= i & -i){
        anst += c[i];
    } 
    return anst;
}
int kth(int k){
    int sum = 0, x = 0;
    //currently have a total of sum that are <= x
    for(int i = 35; i >= 0; i--){
        int powi = (1LL << i);
        if(x + powi <= rang && sum + c[x + powi] < k){
            //within range and within kth
            //we can just use c[x + powi] instead of using get
            //because we know all previous adding to x
            //all are 2 to the jth power where j > i, so powi
            //itself must be the lowbit of x + powi
            x += powi;
            sum += c[x];
        }
    }
    return x + 1;
}
int n, mi, tot, leav, num, INF = 5e5;
signed main(){
    cin>>n>>mi;
    mi += INF;
    while(n--){
        char typ;
        int x;
        cin>>typ>>x;
        if(typ == 'I'){
            if(x - tot + INF < mi){
                continue;
                //KEY BUG!!!
            }
            add(x - tot + INF, 1);
            num++;
        }
        if(typ == 'A'){
            mi -= x;
            tot += x;
        }
        if(typ == 'S'){
            mi += x;
            tot -= x;
            int curmi = kth(1);//smallest
            while(curmi < mi){
                //each will only be erased once we'll be fine
                add(curmi, -1);
                leav++;
                num--;
                //leave
                curmi = kth(1);
            }
        }
        if(typ == 'F'){
            if(x > num)cout<<-1<<endl;
            else cout<<kth(num - x + 1) + tot - INF<<endl;
        }
    }
    cout<<leav<<endl;
    return 0;
}

求赞。