权值线段树啾咪(我也以关注为回报)
查看原帖
权值线段树啾咪(我也以关注为回报)
107527
chenkaiwen楼主2021/8/5 09:59

只过了第一个点

#include <bits/stdc++.h>
using namespace std;
struct as{
	int l,r,ch[2],fa;
	long long sum;
}e[10002021];
int n,Min,Add=0,cnt=1;
int ans=0;
#define ls(k) e[k].ch[0]
#define rs(k) e[k].ch[1]
void up(int k){
	e[k].sum=e[ls(k)].sum+e[rs(k)].sum;
}
void add(int k,int tar){
//	cout<<k<<" "<<tar<<" "<<e[k].sum<<" "<<e[k].l<<" "<<e[k].r<<endl; 
	if(e[k].l==e[k].r){
		if(e[k].l+Add>=Min)
			e[k].sum++;
		else 
			ans++;
		return;
	}
	int mid=e[k].l+e[k].r>>1;
	if(tar<=mid){
		if(!ls(k)){
			ls(k)=++cnt;
			e[ls(k)].l=e[k].l;
			e[ls(k)].r=mid;
			e[ls(k)].fa=k;
		}
		add(ls(k),tar);
	}else{
		if(!rs(k)){
			rs(k)=++cnt;
			e[rs(k)].l=mid+1;
			e[rs(k)].r=e[k].r;
			e[rs(k)].fa=k;
		}
		add(rs(k),tar);
	}
	up(k);
}
int flag=0;
void query(int k,int tar){
	if(e[k].l==e[k].r){
		if(e[k].l+Add>=Min){
			flag=1;
			cout<<e[k].l+Add<<endl;
		}else{
			ans+=e[k].sum;
			e[k].sum=0;
			up(e[k].fa);
		}
		return;
	}
	int mid=e[k].l+e[k].r>>1;
	if(tar<=e[rs(k)].sum){
		query(rs(k),tar);
		if(!flag)query(ls(k),tar-e[rs(k)].sum);
	}else{
		query(ls(k),tar-e[rs(k)].sum);
	}
}
void DEL(int k){
	if(e[k].l==e[k].r){
		if(e[k].l+Add>=Min){
			flag=1;
		}else{
			ans+=e[k].sum;
			e[k].sum=0;
			up(e[k].fa);
		}
		return;
	}
	DEL(ls(k));
	if(!flag)DEL(rs(k));
}
void In(){
	cin>>n>>Min;
	e[1].l=1,e[1].r=1000000000,e[1].fa=0;
	while(n--){
		char t1;int t2;
		cin>>t1>>t2;
		if(t1=='I'){
			if(t2>=Min)
				add(1,t2-Add);
		}else if(t1=='A'){
			Add+=t2;
			flag=0;
			DEL(1);
		}else if(t1=='S'){
			Add-=t2;;
			flag=0;
			DEL(1);
		}else{
			flag=0;
			query(1,t2);
			if(!flag)cout<<-1<<endl;
		}
	}
	cout<<ans<<endl;
}
int main(){
	In();
	return 0;
}
/*
9 10
I 10
I 10
I 10
I 10
S 10
F 1
I 11
F 1
*/
2021/8/5 09:59
加载中...