话说为什么WA了……

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
struct segTree{
	int l,r;
	int val;
	int lz;//lazy_tag
}tree[400005];
struct node{
	int val;
	int id;
	friend bool operator<(node x,node y){
		return x.val<y.val;
	}
}num[100005];
struct Question{
	int opt;
	int l,r;
}Q[100005];
int n,m,a[100005],k;
void build(int id,int l,int r){
	tree[id].l=l;
	tree[id].r=r;
	tree[id].lz=-1;
	if(l==r){
		tree[id].val=a[l];
		return;
	}
	int mid,lc,rc;
	mid=(l+r)/2;
	lc=2*id,rc=2*id+1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	tree[id].val=tree[lc].val+tree[rc].val;
}
void lazy(int id,int val){
	tree[id].val=val*(tree[id].r-tree[id].l+1);
	tree[id].lz=val;
}
void pushup(int id,int val){
	lazy(2*id,val);
	lazy(2*id+1,val);
	tree[id].lz=-1;
}
void update(int id,int l,int r,int val){
	if(l<=tree[id].l&&r>=tree[id].r)
		return lazy(id,val);
	if(tree[id].lz!=-1)
		pushup(id,tree[id].lz);
	int mid,lc,rc;
	mid=(tree[id].l+tree[id].r)/2;
	lc=2*id,rc=2*id+1;
	if(l<=mid)
		update(lc,l,r,val);
	if(r>mid)
		update(rc,l,r,val);
	tree[id].val=tree[lc].val+tree[rc].val;
}
int query(int id,int l,int r){
	if(l<=tree[id].l&&r>=tree[id].r)
		return tree[id].val;
	if(tree[id].lz!=-1)
		pushup(id,tree[id].lz);
	int mid,lc,rc,sum=0;
	mid=(tree[id].l+tree[id].r)/2;
	lc=2*id,rc=2*id+1;
	if(l<=mid)
		sum+=query(lc,l,r);
	if(r>mid)
		sum+=query(rc,l,r);
	return sum;
}
int check(int x){
	memset(tree,0,sizeof(tree));
	memset(a,0,sizeof(a));
	for(int i=x+1;i<=n;i++)
		a[num[i].id]=1;
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int opt=Q[i].opt;
		int l=Q[i].l,r=Q[i].r;
		int sum=query(1,l,r),mid;
		if(opt){
			mid=l+sum-1;
			update(1,l,mid,1);
			update(1,mid+1,r,0);
		}else{
			mid=r-sum;
			update(1,l,mid,0);
			update(1,mid+1,r,1);
		}
	}
	return query(1,k,k);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&num[i].val);
	for(int i=1;i<=n;i++)
		num[i].id=i;
	sort(num+1,num+n+1);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&Q[i].opt,&Q[i].l,&Q[i].r);
	scanf("%d",&k);
	int l=1,r=n,ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid))
			l=mid+1,ans=mid;
		else
			r=mid-1;
	}
	printf("%d\n",num[ans].val+1);
	return 0;
}