自动搬运

查看原文

来自洛谷，原作者为

	浅色调 **

搬运于2025-08-24 21:25:37，当前版本为作者最后更新于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从小到大排序

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