文件详细信息

下载本文件

本文件的大小为 3819 字节。

#include<cstdio>
namespace IO{
	const int ARR_SIZE=1<<24;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		bool flag=true;
		int ch=gc();
		num=0;
		while(ch<48||ch>57){
			if(ch=='-')flag=false;
			ch=gc();
		}
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
		flag||(num=-num);
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a<0)pc('-'),a=-a;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;
const int maxn=100000,maxm=100000;
struct Node{
	Node*ch[2],*fa;
	int val,cnt,size,tag;
}T[maxn*29+maxm+1],*rt=T;
int n,m,a[maxn+1],tot;
void clear(Node*u){
	u->ch[0]=u->ch[1]=u->fa=T;
	u->val=u->cnt=u->size=u->tag=0;
}
void maintain(Node*u){
	u->size=u->ch[0]->size+u->ch[1]->size+u->cnt;
}
void pushdown(Node*u){
	if(!u->tag)return;
	u->val-=u->tag;
	if(u->ch[0]!=T)u->ch[0]->tag+=u->tag;
	if(u->ch[1]!=T)u->ch[1]->tag+=u->tag;
	u->tag=0;
}
int get(const Node*u){
	return u->fa->ch[1]==u;
}
void rotate(Node*x){
	Node*y=x->fa,*z=y->fa;
	const int k=get(x);
	pushdown(y);
	pushdown(x);
	y->ch[k]=x->ch[k^1];
	if(y->ch[k]!=T)y->ch[k]->fa=y;
	(x->ch[k^1]=y)->fa=x;
	x->fa=z;
	if(z!=T)z->ch[y==z->ch[1]]=x;
	maintain(y);
	maintain(x);
}
void splay(Node*x,Node*target){
	for(Node*f=x->fa;f=x->fa,f!=target;rotate(x))
		if(f->fa!=target)
			rotate(get(x)==get(f)?f:x);
	if(target==T)rt=x;
}
Node*insert(const int k,const int cnt=1){
	if(rt==T){
		rt=T+(++tot);
		clear(rt);
		rt->val=k;
		rt->cnt=cnt;
		maintain(rt);
		return rt;
	}
	Node*u=rt,*f=T;
	while(true){
		pushdown(u);
		if(u->val==k){
			u->cnt+=cnt;
			maintain(u);
			maintain(f);
			splay(u,T);
			return u;
		}
		f=u,u=u->ch[u->val<k];
		if(u==T){
			u=T+(++tot);
			clear(u);
			f->ch[f->val<k]=u;
			u->fa=f;
			u->cnt=cnt;
			u->val=k;
			maintain(u);
			maintain(f);
			splay(u,T);
			return u;
		}
	}
}
int rank(const int k){
	int ans=0;
	Node*u=rt;
	while(true){
		pushdown(u);
		if(k<u->val)u=u->ch[0];
		else{
			ans+=u->ch[0]->size;
			if(k==u->val){
				splay(u,T);
				return ans+1;
			}
			ans+=u->cnt;
			u=u->ch[1];
		}
	}
}
Node*kth(int k){
	Node*u=rt;
	while(true){
		pushdown(u);
		if(k<=u->ch[0]->size)u=u->ch[0];
		else{
			k-=u->ch[0]->size+u->cnt;
			if(k<=0){
				splay(u,T);
				return u;
			}
			u=u->ch[1];
		}
	}
}
Node*pre(){
	pushdown(rt);
	Node*u=rt->ch[0];
	pushdown(u);
	while(u->ch[1]!=T)pushdown(u=u->ch[1]);
	splay(u,T);
	return u;
}
void del(const int k){
	rank(k);
	if(rt->cnt>1){
		rt->cnt--;
		maintain(rt);
	}else if(rt->ch[0]==T&&rt->ch[1]==T){
		clear(rt);
		rt=T;
	}else if(rt->ch[0]==T){
		Node*u=rt;
		rt=u->ch[1];
		rt->fa=T;
		clear(u);
	}else if(rt->ch[1]==T){
		Node*u=rt;
		rt=u->ch[0];
		rt->fa=T;
		clear(u);
	}else{
		Node*u=rt,*x=pre();
		u->ch[1]->fa=x;
		x->ch[1]=u->ch[1];
		clear(u);
		maintain(rt);
	}
}
void dfs(Node*u,const int k){
	pushdown(u);
	insert(u->val-k,u->cnt);
	if(u->ch[0]!=T)dfs(u->ch[0],k);
	if(u->ch[1]!=T)dfs(u->ch[1],k);
	clear(u);
}
int main(){
	clear(rt);
	read(n),read(m);
	for(int i=1,a;i<=n;i++){
		read(a);
		insert(a);
	}
	Node*u,*v,*tmp;
	for(int i=1,opt,k;i<=m;i++){
		read(opt),read(k);
		if(opt==1)write(kth(k)->val),pc('\n');
		else{
			u=insert(k),v=insert(k<<1|1);
			splay(u,T),splay(v,u);
			tmp=v->ch[0],v->ch[0]=T,v->tag+=k;
			dfs(tmp,k);
			del(k),del(k+1);
		}
	}
	return 0;
}