bzoj 1503: [NOI2004]郁闷的出纳员 (splay)

#include<bits/stdc++.h>
using namespace std;
const int M = 2e5+10;
const int inf = 0x3f3f3f;
int n,m,sz,rt,mn,add;
int c[M][2],fa[M],tag[M],v[M],siz[M];
 
inline void pushup(int k){
    int l = c[k][0],r = c[k][1];
    siz[k] = siz[l] + siz[r] + 1;
}
 
void rotate(int x,int &k){
    int y = fa[x],z = fa[y],l,r;
    if(c[y][0] == x) l = 0;
    else l = 1;
    r = l^1;
    if(y == k) k = x;
    else {
        if(c[z][0]==y) c[z][0]=x;
        else c[z][1] = x;
    }
    fa[x] = z;fa[y] = x;fa[c[x][r]]=y;
    c[y][l]=c[x][r]; c[x][r]=y;
    pushup(y); pushup(x);
}
 
void splay(int x,int &k){
    while(x != k){
        int y = fa[x],z = fa[y];
        if(y != k){
            if(c[y][0]==x^c[z][0]==y)rotate(x,k);
            else rotate(y,k);
        }
        rotate(x,k);
    }
}
 
inline int Find(int k,int rk){
    int l = c[k][0],r = c[k][1];
    if(siz[r] + 1 == rk) return v[k];
    else if(siz[r] >= rk) return Find(r,rk);
    else return Find(l,rk-siz[r]-1);
}
 
inline void ins(int &k,int val,int last){
    if(k == 0){
        k = ++sz;
        v[k] = val;
        siz[k] = 1;
        fa[k] = last;
        return ;
    }
    if(val < v[k]) ins(c[k][0],val,k);
    else ins(c[k][1],val,k);
    pushup(k);
}
 
inline int del(int &k,int last){
    if(k == 0) return 0;
    int ret = 0;
    if(v[k] + add < mn){
        ret = 1 + siz[c[k][0]] + del(c[k][1],last);
        siz[c[k][1]] = siz[k] - ret;
        k = c[k][1];
        fa[k] = last;
    }
    else{
        ret = del(c[k][0],k);
        siz[k] = siz[k] - ret;
    }
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string op;
    int x;
    add = 0;
    cin>>n>>mn;
    int ans = 0;
    for(int i = 1;i <= n;i ++){
        cin>>op>>x;
        if(op[0] == ‘I‘&&x >= mn) ins(rt,x-add,0),splay(sz,rt);
        else if(op[0] == ‘S‘) add -= x,ans += del(rt,0);
        else if(op[0] == ‘A‘) add += x;
        else if(op[0] == ‘F‘){
            if(siz[rt] < x) cout<<-1<<endl;
            else cout<<Find(rt,x)+add<<endl;
        }
    }
    cout<<ans<<endl;
    return 0;
}