拿动态开点线段树写的

51 $pts$

#include<bits/stdc++.h>
#define M 100001
#define inf 0x3f3f3f3f
#define ls p<<1
#define rs p<<1|1
using namespace std;
inline int read()
{
	int k=0,f=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) f|=c=='-';
	for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c^48);
	return f?-k:k;
}
const int L=-1e7-1,R=1e7+1;
int n,node=1;
struct tree
{
	int lson,rson,val,maxx,minn;
	void clear()
	{
		val=0,maxx=-inf,minn=inf;
	}
}t[M<<2];
void push_up(int p)
{
	t[p].maxx=max(t[t[p].lson].maxx,t[t[p].rson].maxx);
	t[p].minn=min(t[t[p].lson].minn,t[t[p].rson].minn);
}
void update(int p,int l,int r,int x,int k)
{
	t[p].val+=k;
	if(l==r)
	{
		if(t[p].val) t[p].maxx=t[p].minn=l;
		return;
	}
	int mid=(l+r)/2;
	if(x<=mid)
	{
		if(!t[p].lson) t[p].lson=++node;
		update(t[p].lson,l,mid,x,k);
	}
	else
	{
		if(!t[p].rson) t[p].rson=++node;
		update(t[p].rson,mid+1,r,x,k);
	}
	push_up(p);
}
int query_num(int p,int l,int r,int st,int en)
{
	if(st<=l&&r<=en) return t[p].val;
	int mid=(l+r)/2,res=0;
	if(st<=mid&&t[p].lson)  res+=query_num(t[p].lson,l,mid,st,en);
	if(en>mid&&t[p].rson) res+=query_num(t[p].rson,mid+1,r,st,en);
	return res;
}
int query_rank(int p,int l,int r,int x)
{
	if(l==r) return l;
	int mid=(l+r)/2;
	if(t[p].lson&&x<=t[t[p].lson].val) return query_rank(t[p].lson,l,mid,x);
	else return query_rank(t[p].rson,mid+1,r,x-t[t[p].lson].val);
}
int query_max(int p,int l,int r,int st,int en)
{
	if(st<=l&&r<=en) return t[p].maxx;
	int mid=(l+r)/2,MAX=-inf;
	if(t[p].lson&&st<=mid)  MAX=max(MAX,query_max(t[p].lson,l,mid,st,en));
	if(t[p].rson&&en>mid) MAX=max(MAX,query_max(t[p].rson,mid+1,r,st,en));
	return MAX;
}
int query_min(int p,int l,int r,int st,int en)
{
	if(st<=l&&r<=en) return t[p].minn;
	int mid=(l+r)/2,MIN=inf;
	if(t[p].lson&&st<=mid)  MIN=min(MIN,query_min(t[p].lson,l,mid,st,en));
	if(t[p].rson&&en>mid) MIN=min(MIN,query_min(t[p].rson,mid+1,r,st,en));
	return MIN;
}
int main()
{
	n=read(),t[0].clear();
	while(n--)
	{
		int opt=read(),x=read();
		if(opt==1) update(1,L,R,x,1);
		else if(opt==2) update(1,L,R,x,-1);
		else if(opt==3) printf("%d\n",query_num(1,L,R,L,x-1)+1);
		else if(opt==4) printf("%d\n",query_rank(1,L,R,x));
		else if(opt==5) printf("%d\n",query_max(1,L,R,L,x-1));
		else if(opt==6) printf("%d\n",query_min(1,L,R,x+1,R));
	}
	return 0;
}