BZOJ 1503 / Luogu P1486

原题解地址：

https://www.luogu.org/blog/14559/solution-p1486

大致题意：

给出两个整数： n 和 min

你需要写一种数据结构，并维护以下 n 个操作 (k 已给出 $)$ ：

$I$ 命令 ：输入 $,$ 若 k>=min则插入 $k。$

$A$ 命令：将每个数加上 $k。$

$S$ 命令：将每个数减去 $k,$ 并删除所有小于min的数 。

$F$ 命令：查询第 k 大的数。

他——思路__妙，你们可以自己打开去看！下面是我整理的Code！

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF=0x3f3f3f3f;
int n,mn,tot,rt,num,sum,s,k;
char op;

struct Node{
	int l,r,cnt,sz,val,da;
}a[100001];

inline void Update(int x){
	a[x].sz=a[x].cnt+a[a[x].l].sz+a[a[x].r].sz;
}

inline int New(int x){
	tot++;
	a[tot].val=x;
	a[tot].da=rand();
	a[tot].cnt=a[tot].sz=1;
	return tot;
}

inline void Build(){
	New(-INF);
	New(INF);
	rt=1;
	a[1].r=2;
	Update(rt);
}
//右旋 
inline void Zig(int &x){
	int y=a[x].l;
	a[x].l=a[y].r;
	a[y].r=x;
	x=y;
	Update(a[x].r);
	Update(x);
}
//左旋
inline int Zag(int &x){
	int y=a[x].r;
	a[x].r=a[y].l;
	a[y].l=x;
	x=y;
	Update(a[x].l);
	Update(x);
} 

void Insert(int &x,int val){
	if(!x){
		x=New(val);
		Update(x);
		return ;
	}
	if(val==a[x].val){
		a[x].cnt++;
		Update(x);
		return ;
	}
	if(val<a[x].val){
		Insert(a[x].l,val);
		if(a[x].da<a[a[x].l].da)
			Zig(x);
	}
	else{
		Insert(a[x].r,val);
		if(a[x].da<a[a[x].r].da)
			Zag(x);
	}
	Update(x);
}

void Delete(int &x,int val){
	if(!x) return ;
	if(a[x].val==val){
		if(a[x].cnt>1){
			a[x].cnt--;
			Update(x);
			return ;
		}
		if(a[x].l||a[x].r){
			if(!a[x].r||a[a[x].l].da>a[a[x].r].da){
				Zig(x);
				Delete(a[x].r,val);
			}
			else{
				Zag(x);
				Delete(a[x].l,val);
			}
			Update(x);
		}
		else x=0;
		return ;
	}
	if(val<a[x].val)
		Delete(a[x].l,val);
	else Delete(a[x].r,val);
	Update(x);
}

int Find_Rank(int x,int val){
	if(!x) return -1;
	if(a[a[x].l].sz>=val)
		return Find_Rank(a[x].l,val);
	if(a[a[x].l].sz+a[x].cnt>=val)
		return a[x].val;
	return Find_Rank(a[x].r,val-a[x].cnt-a[a[x].l].sz);
}

int Init(int val){
	int x=rt,ans=1;
	while(x){
		if(a[x].val==val){
			ans=x;
			break;
		}
		if(a[x].val<val&&a[x].val>a[ans].val) 
			ans=x;
		if(a[x].val<val) x=a[x].r;
		else x=a[x].l;
	}
	return a[ans].val;
}

int main(){
	scanf("%d%d",&n,&mn);
	Build();
	for(int i=1;i<=n;i++){
		scanf("\n");
		scanf("%c%d",&op,&k);
		if(op=='I')
			if(k-sum>=mn){
				Insert(rt,k-sum);
				num++;
				s++;
			}
		if(op=='F'){
			if(num<k)
				puts("-1");
			else
				printf("%d\n",Find_Rank(rt,num-k+2)+sum);
		}
		if(op=='A')
			mn-=k,sum+=k;
		if(op=='S'){
			mn+=k,sum-=k;
			int a1=mn-1,a2;
			while(Init(a1)!=-INF){
				a2=a1;
				a1=Init(a1);
				Delete(rt,Init(a2));
				num--;
			}
		}
	}
	printf("%d\n",s-num);
	return 0;
}