WA #10权值线段树

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define mid ((l+r)>>1)
using namespace std;
const int INF = 5e6;
const int N = 1e5 + 10;
template<typename TY>
inline void read(TY &s){
	ll x = 0,f = 1;
    char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	s = x * f;
}
struct node{
	int ls,rs;
	ll sum;
}z[N*20];
int cnt,m,q,c,n,root;
void push_up(int rt){
	z[rt].sum = z[z[rt].ls].sum + z[z[rt].rs].sum;
}
void update(int &rt,int l,int r,int x){
	if(!rt) rt = ++cnt;
	if(l == r){
		z[rt].sum++;
		return;
	}
	if(x <= mid) update(z[rt].ls,l,mid,x);
	else update(z[rt].rs,mid+1,r,x);
	push_up(rt);
}
int query(int rt,int l,int r,int k){
	if(l == r){
		return l;
	}
	if(z[z[rt].rs].sum >= k) return query(z[rt].rs,mid+1,r,k);
	else return query(z[rt].ls,l,mid,k-z[z[rt].rs].sum); 
}
int b[N],a[N],t;
pair<int,int> qu[N];
signed main(){
	read(m); read(q);
	for(int i=1;i<=m;i++){
		read(a[i]);
		b[++t] = a[i];
	}
	for(int i=1;i<=q;i++){
		read(qu[i].first); read(qu[i].second);
		if(qu[i].first == 2) b[++t] = qu[i].second;
	}
	sort(b+1,b+t+1);
	t = unique(b+1,b+t+1) - (b + 1);
	for(int i=1;i<=m;i++){
		int k = lower_bound(b+1,b+t+1,a[i]) - b;
		update(root,1,INF,k);
	}
	for(int i=1;i<=q;i++){
		if(qu[i].first==2){
			int k = lower_bound(b+1,b+t+1,qu[i].second) - b;
			update(root,1,INF,k);
		}
		else{
			int p = query(root,1,INF,qu[i].second);
			cout << b[p] << "\n";
		}
	}
	return 0;
}