输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。

#include <cstdio>

#include <cstring>

#include <iostream>

#define lson x<<1

#define rson x<<1|1

using namespace std;

const int maxn=100010;

int n,m,now,pos;

int s[maxn<<2],tag[maxn<<2],pa[maxn],pb[maxn],op[maxn],v[maxn];

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

inline void pushdown(int l,int r,int x)

{

	if(tag[x]!=-1)

	{

		int mid=(l+r)>>1;

		s[lson]=(mid-l+1)*tag[x],s[rson]=(r-mid)*tag[x],tag[lson]=tag[rson]=tag[x];

		tag[x]=-1;

	}

}

void build(int l,int r,int x)

{

	tag[x]=-1;

	if(l==r)

	{

		s[x]=(v[l]>=now);

		return ;

	}

	int mid=(l+r)>>1;

	build(l,mid,lson),build(mid+1,r,rson);

	s[x]=s[lson]+s[rson];

}

void updata(int l,int r,int x,int a,int b,int c)

{

	if(a>b)	return ;

	if(a<=l&&r<=b)

	{

		s[x]=(r-l+1)*c,tag[x]=c;

		return ;

	}

	pushdown(l,r,x);

	int mid=(l+r)>>1;

	if(a<=mid)	updata(l,mid,lson,a,b,c);

	if(b>mid)	updata(mid+1,r,rson,a,b,c);

	s[x]=s[lson]+s[rson];

}

int query(int l,int r,int x,int a,int b)

{

	if(a<=l&&r<=b)	return s[x];

	pushdown(l,r,x);

	int mid=(l+r)>>1;

	if(b<=mid)	return query(l,mid,lson,a,b);

	if(a>mid)	return query(mid+1,r,rson,a,b);

	return query(l,mid,lson,a,b)+query(mid+1,r,rson,a,b);

}

bool check()

{

	build(1,n,1);

	int i,a;

	for(i=1;i<=m;i++)

	{

		a=query(1,n,1,pa[i],pb[i]);

		if(op[i])	updata(1,n,1,pa[i],pa[i]+a-1,1),updata(1,n,1,pa[i]+a,pb[i],0);

		else	updata(1,n,1,pa[i],pb[i]-a,0),updata(1,n,1,pb[i]-a+1,pb[i],1);

	}

	return query(1,n,1,pos,pos);

}

int main()

{

	n=rd(),m=rd();

	int i,l=1,r=n+1;

	for(i=1;i<=n;i++)	v[i]=rd();

	for(i=1;i<=m;i++)	op[i]=rd(),pa[i]=rd(),pb[i]=rd();

	pos=rd();

	while(l<r)

	{

		now=(l+r)>>1;

		if(check())	l=now+1;

		else	r=now;

	}

	printf("%d",l-1);

	return 0;

}