```cpp
/*
Author: EnderDeer
Online Judge: Luogu
*/
#include<bits/stdc++.h>
#define int long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
int read(){
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
return s * w;
}
mt19937 rnd(1919810);
struct node{
int l;
int r;
int w;
int key;
int siz;
}e[300010];
int cnt,rt;
int tot;
int ans;
int newnode(int w){
cnt ++;
e[cnt].w = w;
e[cnt].key = rnd();
e[cnt].siz = 1;
return cnt;
}
void update(int i){
e[i].siz = e[e[i].l].siz + e[e[i].r].siz + 1;
}
void split(int i,int w,int &x,int &y){
if(!i){
x = y = 0;
return ;
}
if(e[i].w <= w){
x = i;
split(e[i].r,w,e[i].r,y);
}
else {
y = i;
split(e[i].l,w,x,e[i].l);
}
update(i);
}
void split1(int i,int siz,int &x,int &y){
if(!i){
x = y = 0;
return ;
}
if(e[e[i].l].siz < siz){
x = i;
split1(e[i].r,siz - e[e[i].l].siz - 1,e[i].r,y);
}
else {
y = i;
split1(e[i].l,siz,x,e[i].l);
}
update(i);
}
int merge(int x,int y){
if(!x || !y)return x + y;
if(e[x].key > e[y].key){
e[x].r = merge(e[x].r,y);
update(x);
return x;
}
else {
e[y].l = merge(x,e[y].l);
update(y);
return y;
}
}
int x,y,z;
void ins(int w){
tot ++;
split(rt,w,x,y);
rt = merge(merge(x,newnode(w)),y);
}
void del(int w){
tot --;
split(rt,w,x,z);
split(x,w - 1,x,y);
y = merge(e[y].l,e[y].r);
rt = merge(merge(x,y),z);
}
int getnum(int rk){
if(e[rt].siz < rk)return -1;
split1(rt,e[rt].siz - rk,x,y);
split1(y,1,y,z);
int s = e[y].w;
rt = merge(merge(x,y),z);
return s;
}
int n,minn;
void dfs(int x,int w){
if(!x)return ;
e[x].w += w;
dfs(e[x].l,w);
dfs(e[x].r,w);
}
signed main(){
cin>>n>>minn;
for(int i = 1;i <= n;i ++){
char op;
int k;
scanf(" %c ",&op);
k = read();
if(op == 'I'){
if(k >= minn)ins(k);
}
else if(op == 'A'){
dfs(rt,k);
}
else if(op == 'S'){
split(rt,minn + k - 1,x,rt);
ans += e[x].siz;
dfs(rt,-k);
}
else {
printf("%lld\n",getnum(k));
}
}
cout<<ans;
return 0;
}
```
by EDqwq @ 2021-02-22 12:29:45
两个操作次数近乎一样的点，却是三倍的时间差，说明我这个程序有着很大的常数（确信
by EDqwq @ 2021-02-22 12:33:25
[~~火车头~~](https://www.luogu.com.cn/paste/32ibwm6j)
by 天南星魔芋 @ 2021-02-22 12:34:42
@[林深时x见鹿](/user/294562) 你确定你这个dfs不会造成O(n)平衡树？
我感觉这题应该要打标记
by _5011_ @ 2021-02-22 12:41:47
暴力取min删除可以均摊，直接dfs肯定是O(n)平衡树
by _5011_ @ 2021-02-22 12:42:56
@[w33z8kqrqk8zzzх33](/user/91127) 我之前就是打标记，但是这道题暴力dfs次数不大于100次啊/yiw
by EDqwq @ 2021-02-22 12:43:58
~~那可能是你们学校机子带不动3e7~~
~~写严格O(nlogn)吧~~
by _5011_ @ 2021-02-22 12:45:37
或者你去学校oj上看看有没有这个限制？
by _5011_ @ 2021-02-22 12:46:42
@[w33z8kqrqk8zzzх33](/user/91127) 话说如果要打标记怎么写啊，因为他每次加入一个数是并没有被更改过的啊，如果加入就修改，那时间复杂度更高了
by EDqwq @ 2021-02-22 12:47:20
@[w33z8kqrqk8zzzх33](/user/91127) 我草，好像真没有
by EDqwq @ 2021-02-22 12:47:43