rt

修了半天不re了，，，但他奶奶的全wa了

寄！

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int n,m,op[N],val[N],ans;//op原数组/val二分数组 
int Q;
int sum[N * 8], lazy[N * 8];//lazy标记节点相较子节点变化量 

struct number {
	int opt,l,r;
};//修改信息 
number q[N];

void pushup(int o)//求o节点sum（用于向上更新） 
{
	sum[o] = sum[o << 1] + sum[o << 1 | 1];
}

void pushdown(int o, int l, int r)//对o树[l,r]节点lazy下传 
{
	if(lazy[o] == 0) return;
	int mid = (l + r) >> 1;
	lazy[o << 1] += lazy[o], lazy[o << 1 | 1] += lazy[o];
	sum[o << 1] += lazy[o] * (mid - l + 1), sum[o << 1 | 1] += lazy[o] * (r - mid);
	lazy[o] = 0;
}

void build_tree(int o, int l, int r)//建父节点为o的树，范围[l,r]
{
	if (l == r)
	{
		sum[o] = op[l];
		return;
	}
	int mid = (l + r) >> 1;
	build_tree(o << 1, l, mid);
	build_tree(o << 1 | 1, mid + 1, r);	
	pushup(o);//建子树后进行更新 
}

void update(int o, int l, int r, int x, int y, int k)//对o树[i,j]节点中的[x,y]的数改为k 
{
	if(l > y || r < x) return;
	if (x <= l && y >= r)//包含的节点进行更新
	{
		sum[o] = k * (r - l + 1);
		lazy[o] = k;
		return;	
	}
	if (lazy[o]) pushdown(o, l, r);//当前节点lazy尚未下传 
	int mid = (l + r) >> 1;
	if (x <= mid) update(o << 1, l, mid, x, y, k);
	if (y > mid) update(o << 1 | 1, mid + 1, r, x, y, k);
	pushup(o);//更新子树后更新节点 
}

void query(int o, int l, int r, int x, int y)//对o树[i,j]节点中的[x,y]的数加求和 
{
	if(l > y || r < x) return;
	if (x <= l && y >= r)//包含的节点更新答案 
	{
		ans += sum[o];
		return;	
	}	
	if (lazy[o]) pushdown(o, l, r);//当前节点lazy尚未下传 
	int mid = (l + r) >> 1;
	if (x <= mid) query(o << 1, l, mid, x, y);
	if (y > mid) query(o << 1 | 1, mid + 1, r, x, y);
}

inline bool check(int mid,int pos) //检查答案 
{
	for ( int i=1; i<=n; i++ ) //数组中大于x的设为1，小于设为0
	{ 
		if(mid > val[i]) 
			op[i] = 0;
		else op[i] = 1;
	}
	
	build_tree(1, 1, n);//1为根，建树范围[1,n] 
	
	for ( int i=1; i<=m; i++ ) 
	{
		int opt = q[i].opt;
		int l = q[i].l;
		int r = q[i].r;
		if(!opt)//升序排序 
		{
			ans = 0;
			query(1, 1, n, l, r);
			int gs = ans;
			update(1, 1, n, l, r-gs, 0);
			update(1, 1, n, r-gs+1, r, 1);
		}
		if(opt)//降序排序 
		{
			ans = 0;
			query(1, 1, n, l, r);
			int gs = ans;
			update(1, 1, n, l, l+gs-1, 1);
			update(1, 1, n, l+gs, r, 0); 
		}
	}
	ans=0;
	query(1, 1, n, pos, pos);
	if(ans) return true;
	return false;
}

int main() {
	cin >> n >> m;
	for ( int i=1; i<=n; i++ )
		cin >> val[i];
	for ( int i=1; i<=m; i++ )
		cin >> q[i].opt >> q[i].l >> q[i].r;
	
	cin >> Q;

	int l = 1,r = n;//二分答案 
	int now;
	while(l <= r) 
	{
		int mid = (l + r) / 2;
		if( check(mid , Q) ) 
		{
			now = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	} 
	
	cout << now;
	return 0;
}