BZOJ1503郁闷的出纳员(权值线段树)

这道题建立权值线段树，可添加新点

题目链接：

https://www.luogu.org/problem/P1486

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

权值线段树学习博客：https://blog.csdn.net/qq_39565901/article/details/81782611

题解博客：https://blog.csdn.net/qq_41603898/article/details/94590010

分析: 建立权值线段树维护区间出现的数字个数cnt，lazy=1表示区间没有数。维护一个全局偏移量add

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 3;
const int base = 2e5 + 3;
struct T {
	int l,r,cnt,lazy;
}t[maxn<<2];
void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r,t[p].cnt=t[p].lazy=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(p*2,l,mid); build(p*2+1,mid+1,r); 
}
void cal(int p)
{
	if(!t[p].lazy) return;
	t[p].lazy=t[p*2].cnt=t[p*2+1].cnt=0;
	t[p*2].lazy=t[p*2+1].lazy=1;
}
void Insert(int p,int x)
{
	if(t[p].l==t[p].r) {
		if(t[p].l==x) t[p].cnt++;
		return;
	}
	cal(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(x<=mid) Insert(p*2,x); 
	else Insert(p*2+1,x);
	t[p].cnt=t[p*2].cnt+t[p*2+1].cnt;
}
void update(int p,int x)
{
	if(t[p].r<x) {
		t[p].cnt=0,t[p].lazy=1; return;
	} 
	if(t[p].l==t[p].r) {
		if(t[p].r<x) t[p].cnt=0;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	cal(p);
	update(p*2,x);
	if(x>mid) update(p*2+1,x);
	t[p].cnt=t[p*2].cnt+t[p*2+1].cnt;
}
int query(int p,int k)
{
	if(t[p].l==t[p].r) return t[p].l;
	cal(p);
	if(k<=t[p*2+1].cnt) return query(p*2+1,k);
	else return query(p*2,k-t[p*2+1].cnt);
}
int main()
{
	int n,minv,num=0,k,add=0;
	char op[2];
	scanf("%d%d",&n,&minv);
	build(1,0,maxn);
	for(int i=1;i<=n;i++) {
		scanf("%s%d",op,&k);
		if(op[0]=='I') {
			if(k<minv) continue;
			num++;
			Insert(1,k-add+base);
		}
 		else if(op[0]=='A') add+=k;
 		else if(op[0]=='S') {
 			add-=k;	
			update(1,minv-add+base);
		}
		else {
			if(k>t[1].cnt) printf("-1\n");
			else printf("%d\n",query(1,k)+add-base);
		}
   	} 
   	printf("%d",num-t[1].cnt);
	return 0;
}