平衡树，裸题。
我们维护一下加法标记，然后剩下的就乱搞搞就好了。 这里使用了\(splay\)实现。My Code:
#include#define il inlineconst int maxn = 1e5 + 10;const int inf = 0x3f3f3f3f;using namespace std;int n,m,i,j,k,root,add,tot,q,x,mn,padd,pnow; int fa[maxn],ch[maxn][2],val[maxn],size[maxn],cnt[maxn]; il void push_up(int o) { size[o] = size[ch[o][0]] + size[ch[o][1]] + cnt[o]; return;} il int which(int o) { return ch[fa[o]][1] == o; } il void clear(int o) { ch[o][0] = ch[o][1] = 0; fa[o] = size[o] = cnt[o] = val[o] = 0; return;} il void rotate(int o) { int f = fa[o],gf = fa[f],whi = which(o); ch[f][whi] = ch[o][whi ^ 1]; fa[ch[f][whi]] = f; ch[o][whi ^ 1] = f; fa[f] = o;fa[o] = gf; if(gf) ch[gf][ch[gf][1] == f] = o; push_up(f);push_up(o); return;}il void splay(int o,int goal) { for(int f;(f = fa[o]) != goal;rotate(o)) { if(fa[f] != goal) rotate(which(f) == which(o) ? f : o); } if(!goal) root = o; return;} il void insert(int v) { if(!root) { val[++tot] = v;cnt[tot] = 1;push_up(tot); root = 1;return; } int now = root,f = 0; while(1) { if(val[now] == v) { ++cnt[now]; push_up(now);push_up(f); splay(now,0);return; } f = now,now = ch[now][val[now] < v]; if(!now) { val[++tot] = v;cnt[tot] = 1; ch[f][val[f] < v] = tot;fa[tot] = f; push_up(tot);push_up(f); splay(tot,0);return; } }} il int get_rank(int k) { int now = root,res = 0; while(1) { if(k < val[now]) { now = ch[now][0]; } else { res += size[ch[now][0]]; if(k == val[now]) {splay(now,0);return res + 1;} res += cnt[now]; now = ch[now][1]; } }} il int get_kth(int k) { int now = root; while(1) { if(ch[now][0] && k <= size[ch[now][0]]) { now = ch[now][0]; } else { k -= size[ch[now][0]] + cnt[now];if(k <= 0) return val[now]; now = ch[now][1]; } }}il int get_id(int k) { int now = root; while(1) { if(k < val[now]) { now = ch[now][0]; } else { if(k == val[now]) return now; now = ch[now][1]; } }} il int get_prev() { int now = ch[root][0]; while(ch[now][1]) now = ch[now][1]; return now;}il int get_succ() { int now = ch[root][1]; while(ch[now][0]) now = ch[now][0]; return now; } il void erase(int k) { get_rank(k);if(cnt[root] > 1) {--cnt[root];return;} if(!ch[root][0] && !ch[root][1]) { clear(root);root = 0;return; } if(!ch[root][0]) { int tmp = root; root = ch[root][1]; fa[root] = 0; clear(tmp); return; } if(!ch[root][1]) { int tmp = root; root = ch[root][0]; fa[root] = 0; clear(tmp); return; } int x = get_prev(),tmp = root; splay(x,0); ch[x][1] = ch[tmp][1]; fa[ch[x][1]] = x; clear(tmp); push_up(root); return; }int main() { scanf("%d %d",&q,&mn); insert(-inf);insert(inf); while(q--) { char opt[2];int x;scanf("%s%d",opt,&x); switch(opt[0]) { case 'I': if(x < mn) continue;insert(x - add);++padd;break; case 'A': add += x;break; case 'S': { add -= x; insert(mn - add); int x = get_id(-inf),y = get_id(mn - add); splay(x,0);splay(y,x); int pos = ch[x][1]; ch[pos][0] = 0; erase(mn - add); break; } case 'F': { pnow = get_rank(inf) - 2;if(pnow < x) {puts("-1");break;} printf("%d\n",get_kth(pnow + 2 - x) + add); break; } } } pnow = get_rank(inf) - 2; printf("%d\n",padd - pnow); return 0;}