题目描述
在 20162016 年，佳媛姐姐喜欢上了数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要你来帮助她。

这个难题是这样子的：给出一个 11 到 nn 的排列，现在对这个排列序列进行 mm 次局部排序，排序分为两种：

0 l r 表示将区间 [l,r][l,r] 的数字升序排序
1 l r 表示将区间 [l,r][l,r] 的数字降序排序
注意，这里是对下标在区间 [l,r][l,r] 内的数排序。
最后询问第 qq 位置上的数字。

输入格式
输入数据的第一行为两个整数 nn 和 mm，nn 表示序列的长度，mm 表示局部排序的次数。

第二行为 nn 个整数，表示 11 到 nn 的一个排列。

接下来输入 mm 行，每一行有三个整数 \text{op},l,rop,l,r，\text{op}op 为 00 代表升序排序，\text{op}op 为 11 代表降序排序, l,rl,r 表示排序的区间。

最后输入一个整数 qq，表示排序完之后询问的位置

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

输入输出样例
输入 #1复制
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3

输出 #1复制
5
说明/提示
河北省选2016第一天第二题。

对于 30%30% 的数据，n,m\leq 1000n,m≤1000

对于 100%100% 的数据，n,m\leq 10^5n,m≤10
5
，1\leq q\leq n1≤q≤n

我们不能每次都直接排序，但是我们如果是0,1排序呢？只需要log就可以了。就是直接线段树从新排列，然后这道题如果我们二分一个数字，那么把大于等于的置为1，小于等于的置为0就可以了。

然后判断位置q是否为1即可。

为什么具有二分性呢？可以简单地假设一下，如果你二分的答案是1，那么原序列所有的值都转化为了1，所以最后肯定是true。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,m,op[N],l[N],r[N],a[N],b[N],L,R,k;
struct node{int l,r,sum,lazy;}t[N<<2];
inline void push_up(int p){t[p].sum=t[p<<1].sum+t[p<<1|1].sum;}
inline void push_down(int p){
	if(t[p].lazy!=-1){
		t[p<<1].lazy=t[p<<1|1].lazy=t[p].lazy;
		t[p<<1].sum=(t[p<<1].r-t[p<<1].l+1)*t[p].lazy;
		t[p<<1|1].sum=(t[p<<1|1].r-t[p<<1|1].l+1)*t[p].lazy;
		t[p].lazy=-1;
	}
}
void build(int p,int l,int r){
	t[p].l=l; t[p].r=r;	t[p].lazy=-1;
	if(l==r)	return void(t[p].sum=b[l]);
	int mid=l+r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
	push_up(p);
}
void change(int p,int l,int r,int v){
	if(t[p].l==l&&t[p].r==r){t[p].sum=(r-l+1)*v; t[p].lazy=v; return ;}
	int mid=t[p].l+t[p].r>>1;	push_down(p);
	if(r<=mid)	change(p<<1,l,r,v);
	else if(l>mid)	change(p<<1|1,l,r,v);
	else	change(p<<1,l,mid,v),change(p<<1|1,mid+1,r,v);
	push_up(p);
}
int ask(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r)	return t[p].sum;
	push_down(p);	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return ask(p<<1,l,r);
	else if(l>mid)	return ask(p<<1|1,l,r);
	else	return ask(p<<1,l,mid)+ask(p<<1|1,mid+1,r);
}
inline int check(int mid){
	for(int i=1;i<=n;i++)	b[i]=a[i]>=mid;	build(1,1,n);
	for(int i=1;i<=m;i++){
		int num=ask(1,l[i],r[i]);
		if(op[i]){
			if(num)	change(1,l[i],l[i]+num-1,1);
			if(num!=r[i]-l[i]+1)	change(1,l[i]+num,r[i],0);
		}else{
			if(num)	change(1,r[i]-num+1,r[i],1);
			if(num!=r[i]-l[i]+1)	change(1,l[i],r[i]-num,0);
		}
	}
	return ask(1,k,k);
}
signed main(){
	cin>>n>>m; L=1,R=n;
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=1;i<=m;i++)	cin>>op[i]>>l[i]>>r[i]; cin>>k;
	while(L<R){
		int mid=L+R+1>>1;
		if(check(mid))	L=mid;
		else	R=mid-1;
	}
	cout<<L<<endl;
	return 0;
}