思路:
1. 此处的fhq treap的分裂是按照权值分裂然后插入的。将小于k的分为一棵子树,大于等于k的分为另一棵子树。
2. 删除的时候只要将大于等于min的分裂到以root为根的树中,另一部分不用管,扔掉。
3. 维护一个加标记,注意不要忘记某个地方的pushdown和pushup
其他就是fhq treap的基本操作了
#include<bits/stdc++.h>
using namespace std;
#define ls a[x].l
#define rs a[x].r
const int N = 1e5 + ;
int root, tot, ans;
struct tree{
int l, r, atag, val, dat, siz;
}a[N];
struct fhq_treap{
void newnode(int &x, int val){
a[x = ++tot].dat = rand(); a[x].siz = ; a[x].val = val;
}
void addone(int x, int val){
if(!x) return;
a[x].val += val; a[x].atag += val;
}
void up(int x){
if(!x) return ;
a[x].siz = a[ls].siz + a[rs].siz + ;
}
void down(int x){
if(!x) return;
if(a[x].atag) addone(ls, a[x].atag), addone(rs, a[x].atag);
a[x].atag = ;
}
void Merge(int &x, int l, int r){
if(!l || !r) x = l + r;
else if(a[l].dat < a[r].dat) down(x = l), Merge(rs, rs, r), up(x);
else down(x = r), Merge(ls, l, ls), up(x);
}
void split(int x, int k, int &l, int &r){
if(!x) l = r = ;
else{
down(x);
if(a[x].val < k) l = x, split(rs, k, rs, r);
else r = x, split(ls, k, l, ls);
}
up(x);
}
void ins(int val){
int x;
newnode(x, val);
int l, r;
split(root, val, l, r); Merge(l, l, x); Merge(root, l, r);
}
int getval(int x, int rank){
if(x == ) return -;
down(x);
if(a[rs].siz >= rank) return getval(rs, rank);
if(a[rs].siz + >= rank) return a[x].val;
return getval(ls, rank - a[rs].siz - );
}
void del(int val){
int l;
split(root, val, l, root);
}
}treap;
int n, lim, k;
char ch[];
int main(){
scanf("%d%d", &n, &lim);
while(n--){
scanf("%s%d", ch, &k);
if(ch[] == 'I'){
if(k >= lim) treap.ins(k), ans++;
}
else if(ch[] == 'A') treap.addone(root, k);
else if(ch[] == 'S') treap.addone(root, -k), treap.del(lim);
else printf("%d\n", treap.getval(root, k));
}
printf("%d\n", ans - a[root].siz);
return ;
}