http://www.lydsy.com/JudgeOnline/problem.php?id=1503

Brief description:

略。）

Analysis:

测试模板。）

//}/* .................................................................................................................................. */
 
namespace SBT{
    const int NN = int(1e5) + 9;
    int c[2][NN], sz[NN], ky[NN], tot;
#define lx l[x]
#define rx r[x]
#define l c[d]
#define r c[!d]
#define kx ky[x]
#define sx sz[x]
#define d 0
    int new_node(int v = 0){
        int x=++tot;lx=rx=0;
        sx=1;kx=v;
        return x;
    }
 
    void upd(int x){
        sx=sz[lx]+1+sz[rx];
    }
#undef d
    void rot(int &x,int d){
        int y=rx;rx=l[y];l[y]=x;
        upd(x),upd(y),x=y;
    }
 
    void fix(int &x,int d){
        if (sz[l[lx]] > sz[rx]) rot(x,!d);
        else{
            if (sz[r[lx]] > sz[rx]) rot(lx,d),rot(x,!d);
            else return;
        }
        d=0,fix(lx,0),fix(rx,1);
        fix(x,0),fix(x,1);
    }
#define d 0
 
    int mini(int x){
        if (lx) return mini(lx);
        return ky[x];
    }
 
    void iod(int x){
        if (!x) return;
        iod(lx); printf("%d ", ky[x]); iod(rx);
    }
 
    void Ins(int &x,int v){
        if(!x) x = new_node(v);
        else{
            ++sz[x]; Ins(c[v>kx][x],v);
            fix(x,v>=kx);
        }
    }
 
    int d_key; void Del(int &x,int v){
        --sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){
            if(!lx||!rx) d_key = kx, x = lx | rx;
            else Del(lx,v+1), kx = d_key;
        }
        else Del(c[v>kx][x],v);
    }
 
    int Rank(int x,int v){
        int z=0;while(x){
            if(kx<v){
                z+=sz[lx]+1;
                x=rx;
            }
            else x=lx;
        }
        return z;
    }
 
    int Select(int x,int k){
        if (sz[lx] == k) return ky[x];
        return sz[lx]>k?Select(lx,k):Select(rx,k-sz[lx]-1);
    }
 
    bool Find(int x,int v){
        if (!x) return 0;if (kx==v) return 1;
        return Find(c[v>kx][x],v);
    }
 
    void Init(){
        tot = 0;
    }
 
#undef d
#undef l
#undef r
#undef lx
#undef rx
#undef sx
#undef kx
} using namespace SBT;
 
int n, b, d, rt, cnt;
 
void Insert(int v){
    if (v < b) return;
    v -= d; Ins(rt, v);
}
 
int main(){
 
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    while (~scanf("%d %d", &n, &b)){
 
        Init(); rt = cnt = 0;
 
        DO(n){
            char cmd; RC(cmd); int k; RD(k); switch(cmd){
                case 'I':
                    Insert(k);
                    break;
                case 'A':
                    d += k;
                    break;
                case 'S':
                    d -= k;
                    while (rt && mini(rt) + d < b) Del(rt, mini(rt)),++cnt;
                    break;
                default:
                    if (k > sz[rt]) puts("-1");
                    else{
                        OT(Select(rt,sz[rt]-k)+d);
                    }
            }
        }
 
        OT(cnt);
    }
}

Posted by xiaodao
Category: 日常
Tags: offset