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

浅色调 · 2018-03-13 16:34:05 · 题解

最近比较懒惰，然后学了一波pb_ds。于是，本题就可以用pb_ds中的rb_tree做了，普通平衡树那题也用pb_ds水了一波ac。（noi赛制下pb_ds是可以用的，联赛貌似不行不过用来对拍是蛮不错的选择，splay还是得掌握的。）

所需声明及头文件：

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<pt,null_type,less< pt >,rb_tree_tag,tree_order_statistics_node_update> rbtree;

解释及用途：

int 关键字类型

null_type无映射(低版本g++为null_mapped_type)

less<int>从小到大排序

rb_tree_tag 红黑树（splay_tree_tag）

tree_order_statistics_node_update结点更新

插入t.insert();

删除t.erase();

Rank:t.order_of_key();

第K值:t.find_by_order();

前驱:t.lower_bound();

后继t.upper_bound();

a.join(b)b并入a 前提是两棵树的key的取值范围不相交

a.split(v,b)key小于等于v的元素属于a，其余的属于b

T.lower_bound(x) >=x的min的迭代器

T.upper_bound((x) >x的min的迭代器

T.find_by_order(k) 有k个数比它小的数

代码：

#include<cstdio>  
#include<iostream>  
#include<ext/pb_ds/assoc_container.hpp>  
#include<ext/pb_ds/tree_policy.hpp>  
using namespace __gnu_pbds;  
using namespace std;  
struct node{  
    int v,id;  
    node(int a,int b){v=a;id=b;}  
    bool operator >(node b) const  
    {return v==b.v?id>b.id:v>b.v;}  
};  
tree<node,null_type,greater<node>,rb_tree_tag,tree_order_statistics_node_update> T,TE;  
int main(){  
    int n,m,k,s=0,q,ans=0;  
    char c[10];  
    scanf("%d%d",&n,&m);  
    while(n--){  
        cin>>c[0];scanf("%d",&k);  
        if(*c=='I') {k+=s;if(k>=m) T.insert(node(k,n));}  
        else if(*c=='A') m-=k,s-=k;  
        else if(*c=='S'){  
            m+=k,s+=k;  
            T.split(node(m,-1),TE);  
            ans+=TE.size();  
        }  
        else if(*c=='F')      
            printf(k>T.size()?"-1\n":"%d\n",T.find_by_order(k-1)->v-s);  
    }  
    printf("%d\n",ans);  
    return 0;  
}