每日归档： 2018年11月9日

（似乎很少看见权值线段树的做法的样子。但是权值线段树如果动态开点、大胆卡常的话，是可以跑得飞快的。）
首先看一下题面，发现值域很小，很容易就可以想到用权值线段树维护。
支持：单点加，区间清零，查询第k大的权值线段树。
当然这题有一些细节。
一：如果初始工资低于工资下限，那么这个人就不存在。
二：维护的是第\(k\)大的而非第\(k\)小的。
三：由于是严格小于工资下限，要注意边界的开闭性。最好将公式写出来。

#include<iostream>
#include<cstdio>
using namespace std;
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
#define MID ((L+R)>>1)
#define LLEN (MID-L+1)
#define RLEN (R-MID) 
//支持：单点加，区间清零，查询第k大的权值线段树。
int tr[2000005],cnt=0; 
inline void updt(int X){
	tr[X]=tr[LS]+tr[RS];
}
inline void pshd(int X,int L,int R){
	if(!tr[X]){
		tr[LS]=tr[RS]=0;
	}
}
inline void add(int X,int L,int R,int A){
	if(L==R){
		++tr[X];
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		add(LS,L,MID,A);
	}else{
		add(RS,MID+1,R,A);
	}
	updt(X);
}
inline void clr(int X,int L,int R,int A,int B){
	if(A<=L&&R<=B){
		cnt+=tr[X];
		tr[X]=0;
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		clr(LS,L,MID,A,B);
	}
	if(B>MID){
		clr(RS,MID+1,R,A,B);
	}
	updt(X);
}
inline int srch(int X,int L,int R,int K){
	if(L==R){
		return L;
	}
	pshd(X,L,R);
	if(tr[RS]<K){
		return srch(LS,L,MID,K-tr[RS]);
	}else{
		return srch(RS,MID+1,R,K);
	}
}
inline int qry(int X,int L,int R,int A,int B){
	if(A<=L&&R<=B){
		return tr[X];
	}
	pshd(X,L,R);
	int rt=0;
	if(A<=MID){
		rt+=qry(LS,L,MID,A,B);
	}
	if(B>MID){
		rt+=qry(RS,MID+1,R,A,B);
	}
	updt(X);
	return rt;
}
//1 k 插入大小为k的点
//2 k 全部数加上k
//3 k 全部数减去k
//4 k 查询第k大的值 
int n,m,tg=0,k;
char op[4];
void init(){
	scanf("%d%d",&n,&m);
	--m;
	for(int i=1;i<=n;++i){
		cin>>op;
		scanf("%d",&k);
		if(op[0]=='I'){
			//注意大于与大等于。 
			if(k>m){
				add(1,1,300001,k+100001+tg);
			}
		}else if(op[0]=='A'){
			tg-=k; 
		}else if(op[0]=='S'){
			tg+=k;
			clr(1,1,300001,1,m+100001+tg);
		}else if(op[0]=='F'){
			if(qry(1,1,300001,1,300001)<k){
				puts("-1");
			}else{
				printf("%d\n",srch(1,1,300001,k)-100001-tg);
			}
		}
	}
	printf("%d",cnt);
}
int main(){
	init();
	return 0;
}