我们终于知道了那天所见的TLE线段树的常数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

typedef long long LL;

inline int read()
{
	char c=getchar();int num=0;
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())
		num=num*10+c-'0';
	return num;
}

const int N=1e5+5;

int n,m,pos;
int a[N],b[N];

struct OPT
{
	int opt,l,r;
}opt[N];

#define Root tree[root]
#define lson tree[root].ls
#define rson tree[root].rs
#define Lson tree[lson]
#define Rson tree[rson]
struct Tree
{
	int ls,rs,len;
	int val;bool tag;
}tree[N<<1];
int now_node,ROOT;

void build(int &root,int l,int r)
{
	if(!root) root=++now_node;
	Root.len=r-l+1;Root.tag=0;
	if(l==r)
	{
		Root.val=b[l];
		return;
	}
	int mid=(l+r)>>1;
	build(lson,l,mid),build(rson,mid+1,r);
	Root.val=Lson.val+Rson.val;
}

void pushdown(int root)
{
	Lson.val=Root.val?Lson.len:0;
	Rson.val=Root.val?Rson.len:0;
	Lson.tag=Rson.tag=1;
	Root.tag=0;
}

void modify(int root,int l,int r,int L,int R,int x)
{
	if(L>R||r<L||l>R) return;
	if(l==L&&R==r)
	{
		Root.val=x*Root.len;
		Root.tag=1;
		return;
	}
	if(Root.tag)
		pushdown(root);
	int mid=(l+r)>>1;
	if(R<=mid)
		modify(lson,l,mid,L,R,x);
	else if(L>mid)
		modify(rson,mid+1,r,L,R,x);
	else
		modify(lson,l,mid,L,mid,x),modify(rson,mid+1,r,mid+1,R,x);
	Root.val=Lson.val+Rson.val;
}

int query(int root,int l,int r,int L,int R)
{
	if(l==r)
		return Root.val;
	if(Root.tag)
		pushdown(root);
	int mid=(l+r)>>1;
	if(R<=mid)
		return query(lson,l,mid,L,R);
	else if(L>mid)
		return query(rson,mid+1,r,L,R);
	else
		return query(lson,l,mid,L,mid)+query(rson,mid+1,r,mid+1,R);
}

int check(int x)
{
	for(int i=1;i<=n;++i)
		b[i]=a[i]>=x?1:0;
	build(ROOT,1,n);
	for(int i=1,cnt;i<=m;++i)
	{
		cnt=query(ROOT,1,n,opt[i].l,opt[i].r);
		if(opt[i].opt==0)
		{
			modify(ROOT,1,n,opt[i].l,opt[i].r-cnt,0);
			modify(ROOT,1,n,opt[i].r-cnt+1,opt[i].r,1);
		}
		else
		{
			modify(ROOT,1,n,opt[i].l,opt[i].l+cnt-1,1);
			modify(ROOT,1,n,opt[i].l+cnt,opt[i].r,0);
		}
	}
	return query(ROOT,1,n,pos,pos);
}

int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=m;++i)
		opt[i].opt=read(),opt[i].l=read(),opt[i].r=read();
	pos=read();
	int l=1,r=n,mid,ans;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid))
			l=mid+1,ans=mid;
		else
			r=mid-1;
	}
	cout<<ans;
	return 0;
}