https://www.luogu.com.cn/problem/P2824 搞了一上午了tat

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int seg[400010];
int n,m,q;
int op[N],l[N],r[N];
int a[N],f[N];
int tag[N];
void build_tree(int l,int r,int u)
{
	tag[u]=0;
	if(l==r)
	{
		seg[u]=f[l];
		return;
	}
	
	int mid=(l+r)>>1;
	build_tree(l,mid,u<<1);
	build_tree(mid+1,r,u<<1|1);
	seg[u]=seg[u<<1]+seg[u<<1|1];
}
void pushdown(int u,int l,int r)
{
	if(!tag[u]) return;
	int m=(l+r)>>1;
	if(tag[u]==1)
	{
		seg[u<<1]=m-l+1;seg[u<<1|1]=r-m; 
		tag[u<<1]=tag[u<<1|1]=1;
	}
	else seg[u<<1]=seg[u<<1|1]=0,tag[u<<1]=tag[u<<1|1]=2;
}
int query(int l,int r,int ll,int rr,int u)
{
	if(l>=ll && r<=rr) return seg[u];
	if(l>rr || r<ll) return;
 	int mid=(l+r)>>1;
	int ans=0;
	if(mid>=ll) ans+=query(l,mid,ll,rr,u<<1);
	if(mid+1<=rr) ans+=query(mid+1,r,ll,rr,u<<1|1);
	return ans;
}
void update(int l,int r,int ll,int rr,int u,int p)
{
	if(l>=ll && r<=rr)
	{
		tag[u]=p;
		if(p==1) seg[u]=(r-l+1);
		else seg[u]=0;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=ll) update(l,mid,ll,rr,u<<1,p);
	if(mid+1<=rr) update(mid+1,r,ll,rr,u<<1|1,p);
	seg[u]=seg[u<<1]+seg[u<<1|1];
}
bool check(int k)
{
	for(int i=1;i<=n;i++)
	{
		if(a[i]>k) f[i]=1;
		else f[i]=0;
	}
	build_tree(1,n,1);
	for(int i=1;i<=m;i++)
	{
		int cnt=query(1,n,l[i],r[i],1);
		if(op[i])
		{
			update(1,n,l[i],l[i]+cnt-1,1,1);
			update(1,n,l[i]+cnt,r[i],1,2);
		}
		else
		{
			update(1,n,l[i],r[i]-cnt,1,2);
			update(1,n,r[i]-cnt+1,r[i],1,1);
		}
	}
	return query(1,n,q,q,1);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&op[i],&l[i],&r[i]);
	int ll=1,rr=n,best=-1;
	scanf("%d",&q);
	while(ll<=rr)
	{
		int mid=(ll+rr)/2;
		if(check(mid)) ll=mid+1,best=mid;
		else rr=mid-1;
	}
	cout<<best<<endl;
	
}