NOI 2006 郁闷的出纳员

HYSBZ_1053

    这个算是平衡树的处女作啦，争取这两天能够练到熟练地敲出平衡树O(∩_∩)O~

    这个题目比较坑人的地方就是题目中明明说“如果初始工资低于下界他将立刻离开公司”，但偏偏最后的结果是不算这部分人的。

    这个题目可以用平衡树做，也可以用线段树做，用线段树的话就以工资为关键字建立线段树，但这样实际上是受工资大小的限制的，如果工资变化幅度比较大的话线段树就还要增加离散化的操作。

#include<stdio.h>
#include<string.h>
#define MAXD 100010
int T, node, left[MAXD], right[MAXD], size[MAXD], key[MAXD], ADD, N, MIN, leave;
void left_rotate(int &T)
{
    int k = right[T];
    right[T] = left[k];
    left[k] = T;
    size[k] = size[T];
    size[T] = size[left[T]] + size[right[T]] + 1;
    T = k;
}
void right_rotate(int &T)
{
    int k = left[T];
    left[T] = right[k];
    right[k] = T;
    size[k] = size[T];
    size[T] = size[left[T]] + size[right[T]] + 1;
    T = k;
}
void Maintain(int &T, int flag)
{
    if(flag == 0)
    {
        if(size[left[left[T]]] > size[right[T]])
            right_rotate(T);
        else if(size[right[left[T]]] > size[right[T]])
            left_rotate(left[T]), right_rotate(T);
        else
            return ;
    }
    else
    {
        if(size[right[right[T]]] > size[left[T]])
            left_rotate(T);
        else if(size[left[right[T]]] > size[left[T]])
            right_rotate(right[T]), left_rotate(T);
        else
            return ;
    }
    Maintain(left[T], 0);
    Maintain(right[T], 1);
    Maintain(T, 1);
    Maintain(T, 0);
}
void add(int &T, int v)
{
    T = ++ node;
    size[T] = 1;
    left[T] = right[T] = 0;
    key[T] = v;
}
void Insert(int &T, int v)
{
    if(T == 0)
    {
        add(T, v);
        return ;
    }
    ++ size[T];
    if(v < key[T])
        Insert(left[T], v);
    else
        Insert(right[T], v);
    Maintain(T, v >= key[T]);
}
int Erase(int &T, int v)
{
    if(T == 0)
        return 0;
    if(key[T] < v)
    {
        int n = size[left[T]] + Erase(right[T], v) + 1;
        T = right[T];
        return n;
    }
    else
    {
        int n = Erase(left[T], v);
        size[T] -= n;
        return n;
    }
}
int select(int &T, int k)
{
    int n = size[left[T]] + 1;
    if(n == k)
        return key[T];
    else if(k < n)
        return select(left[T], k);
    else
        return select(right[T], k - n);
}
void solve()
{
    int i, j, k;
    char b[5];
    T = node = ADD = leave = left[0] = right[0] = size[0] = 0;
    for(i = 0; i < N; i ++)
    {
        scanf("%s%d", b, &k);
        if(b[0] == 'I')
        {
            if(k >= MIN)
                Insert(T, k - ADD);
        }
        else if(b[0] == 'A')
            ADD += k;
        else if(b[0] == 'S')
        {
            ADD -= k;
            leave += Erase(T, MIN - ADD);
        }
        else
        {
            if(k > size[T])
                printf("-1\n");
            else
                printf("%d\n", select(T, size[T] - k + 1) + ADD);
        }
    }
    printf("%d\n", leave);
}
int main()
{
    while(scanf("%d%d", &N, &MIN) == 2)
    {
        solve();
    }
    return 0;
}