bzoj 1503 (权值线段树)

由于蒟蒻实在是ttttttai 菜了，于是开始了学习主席树，权值线段树作为主席树的前置知识，于是蒟蒻各种百度百度，谷歌谷歌，抄网上的代码，然后终于A了这个题目。也还算是有一点收获。

题目：芝麻开门

题意：中文题，不解释。

思路：首先 升工资和降工资 可以用一个偏移量 tmp 来表示，但会有一个问题，因为可以在升工资和降工资之前新增成员，假设一开始就是满员工，那么升工资 tmp 直接 += ，降工资就判断所有小于minn的，然后删除（也就是置0）就ok了。 而对于中间的新增成员，更新的结点就应该是    (新成员工资 - tmp) （因为最后输出的时候是  原工资+偏移量，所以对于新成员，最开始时要提前减去已经存在的偏移量），但是这样很可能存在一个问题，为负。 故一开始就需要设立一个base，来避免这个问题；

AC代码：

#include<bits/stdc++.h>
#define debug(x) cout << "[" << #x <<": " << (x) <<"]"<< endl
#define pii pair<int,int>
#define clr(a,b) memset((a),b,sizeof(a))
#define rep(i,a,b) for(int i = a;i < b;i ++)
#define pb push_back
#define MP make_pair
#define LL long long
#define ull unsigned LL
#define ls i << 1
#define rs (i << 1) + 1
#define INT(t) int t; scanf("%d",&t)

using namespace std;

inline int read()
{
    int x = 0;
    char c = getchar();
    bool flag = 0;
    while(!isdigit(c)){if(c == '-')flag = 1;c = getchar();}
    while(isdigit(c)){x = (x << 3) + (x << 1) + (c ^ 48);c = getchar();}
    return flag ? -x : x;
}

const int maxn = 4e5 + 20;
const int base = 2e5 + 1;
int sum[maxn * 4];
int lazy[maxn * 4];

void pushDown(int i){
    if(lazy[i]){
        sum[i << 1] = sum[i << 1 | 1] = 0;
        lazy[i << 1] = lazy[i << 1 | 1] = 1;
        lazy[i] = 0;
    }
}

void isrt(int pos,int l,int r,int i){
    if(l == r){
        if(l == pos) ++ sum[i];
        return ;
    }
    int mid = (l + r) >> 1;
    pushDown(i);
    if(pos <= mid) isrt(pos,l,mid,i << 1);
    if(pos > mid) isrt(pos,mid + 1,r,i << 1 | 1);
    sum[i] = sum[i << 1] + sum[i << 1 | 1];
}

void udt(int l,int r,int ul,int ur,int i){
    pushDown(i);
    if(ul <= l && r <= ur){
        sum[i] = 0;
        lazy[i] = 1;
        return ;
    }
    int mid = (l + r) >> 1;
    if(ul <= mid) udt(l,mid,ul,ur,i << 1);
    if(ur > mid) udt(mid + 1,r,ul,ur,i << 1 | 1);
    sum[i] = sum[i << 1] + sum[i << 1 | 1];
}

int Kth(int l,int r,int i,int k){
    int mid = (l + r) >> 1;
    pushDown(i);
    if(l == r) return l;
    if(sum[i << 1 | 1] >= k){
        return Kth(mid + 1,r,i << 1 | 1,k);
    }
    else
        return Kth(l,mid,i << 1,k - sum[i << 1 | 1]);
}

int main()
{
    int n,minn; scanf("%d%d",&n,&minn);
    int ans = 0,tmp = 0;
    clr(sum,0); clr(lazy,0);
    while(n --){
        char ch; int k;
        scanf(" %c%d",&ch,&k);
        if(ch == 'I'){
            if(k < minn) continue;
            ++ ans;
            isrt(k - tmp + base,1,maxn - 1,1);                  /// k,k - tmp + base
            //debug(sum[1]);
            //    debug(sum[3]);
        }
        else if(ch == 'A')
            tmp += k;
        else if(ch == 'S'){
            tmp -= k;
            udt(1,maxn - 1,1,minn - tmp + base - 1,1); /// x + tmp < minn,x < minn - tmp，区间是闭区间，所以 minn - tmp + base - 1
        }
        else {
            //debug(sum[1]);
            if(sum[1] < k) printf("-1\n");
            else{
                printf("%d\n",Kth(1,maxn - 1,1,k) - base + tmp);
            }
        }
    }
    printf("%d\n",ans - sum[1]);
    return 0;
}