题意：
给出原始序列in
c=1 查询第v大的值
c=2 插入值v
思路：离散化+权值线段树

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
inline ll lc(ll p){return p<<1;}
inline ll rc(ll p){return p<<1|1;}
const ll Maxn=1e5+2e4+5;
const ll Maxm=3e4+5; 
ll m,q;
ll in[Maxn];
ll a[Maxn];//被离散成的i原来是a[i]
ll c[Maxm],v[Maxm];
ll cnt;
ll num[Maxn<<2];
void pushup(ll p)
{
	num[p]=num[lc(p)]+num[rc(p)];
}
void insert(ll p,ll l,ll r,ll x)
{
//	cout<<p<<" "<<l<<"lr"<<r<<endl;
	if(l==r)
	{
		num[p]++;
		return;
	}
	ll mid=(l+r)>>1;
	if(x<=mid) insert(lc(p),l,mid,x);
	else insert(rc(p),mid+1,r,x);
	pushup(p);
}
ll query(ll p,ll l,ll r,ll x)
{
	if(l==r) return l;
	ll mid=(l+r)>>1;
	if(x<num[lc(p)]) return query(lc(p),l,mid,x);
	else return query(rc(p),mid+1,r,x-num[lc(p)]);
}
ll call(ll p)//p被离散成call(p) 
{
	ll l=1,r=cnt,mid,ans;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(a[mid]==p)
		{
			ans=mid;
			r=mid-1;
		}
		else
		{
			if(a[mid]<p) l=mid+1;
			else r=mid-1;
		}
	}
	return ans;
}
signed main()
{
	scanf("%lld%lld",&m,&q);
	for(ll i=1;i<=m;i++)
	{
		scanf("%lld",&in[i]);
		a[i]=in[i];
	}
	cnt=m;
	for(ll i=1;i<=q;i++)
	{
		scanf("%lld%lld",&c[i],&v[i]);
		if(c[i]==2) a[++cnt]=v[i];
	}
	sort(a+1,a+cnt+1);
	for(ll i=1;i<=m;i++)
	{
		insert(1,1,cnt,call(in[i]));
	}
	for(ll i=1;i<=q;i++)
	{
		if(c[i]==1)
		{
			printf("%lld\n",a[query(1,1,cnt,cnt-v[i])]);
		}
		else insert(1,1,cnt,call(v[i]));
	}
}