记录编号	599871	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 排序	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	4.422 s
提交时间	2025-03-29 17:22:57	内存使用	4.37 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=3e5;
inline int in(){
	char c=getchar(); int x=0,w=1;
	while(c>'9'||c<'0'){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*w;
}
struct node{
	int op,l,r;
}q[N];
int n,m,a[N],k,tag[N<<2],tre[N<<2],st[N];
inline void pushup(int p){
	tre[p]=tre[p<<1]+tre[p<<1|1];
}
void build(int l,int r,int p){
	tag[p]=-1;
	if(l==r){
		tre[p]=st[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
	pushup(p);
}
inline void pushdown(int p,int l,int r){
	if(tag[p]<0) return;
	tag[p<<1]=tag[p<<1|1]=tag[p];
	tre[p<<1]=tag[p]*l;
	tre[p<<1|1]=tag[p]*r;
	tag[p]=-1;
}
void change(int ll,int rr,int val,int l,int r,int p){
	if(l>rr||r<ll) return;
	if(l>=ll&&r<=rr){
		tre[p]=val*(r-l+1);
		tag[p]=val;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(p,mid-l+1,r-mid);
	change(ll,rr,val,l,mid,p<<1);
	change(ll,rr,val,mid+1,r,p<<1|1);
	pushup(p);
}
int query(int ll,int rr,int l,int r,int p){
	if(l>rr||r<ll) return 0;
	if(l>=ll&&r<=rr) return tre[p];
	int mid=(l+r)>>1,asd=0;
	pushdown(p,mid-l+1,r-mid);
	asd+=query(ll,rr,l,mid,p<<1);
	asd+=query(ll,rr,mid+1,r,p<<1|1);
	return asd;
}
inline int jud(int mid){
	for(int i=1;i<=n;i++){
		if(a[i]>=mid) st[i]=1;
		else st[i]=0;
	}
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int l=q[i].l,r=q[i].r;
		int sdf=query(l,r,1,n,1);
		if(q[i].op==0){
			change(r-sdf+1,r,1,1,n,1);
			change(l,r-sdf,0,1,n,1);
		}else{
			change(l,l+sdf-1,1,1,n,1);
			change(l+sdf,r,0,1,n,1);
		}
	}
	return query(k,k,1,n,1);
}
int main(){
	freopen("heoi2016_sort.in","r",stdin);
	freopen("heoi2016_sort.out","w",stdout);
	n=in();
	m=in();
	for(int i=1;i<=n;i++){
		a[i]=in();
	}
	for(int i=1;i<=m;i++){
		q[i].op=in();
		q[i].l=in();
		q[i].r=in();
	}
	k=in();
	int ll=1,rr=n,ans=0;
	while(ll<=rr){
		int mid=(ll+rr)>>1;
		if(jud(mid)) ll=mid+1,ans=mid;
		else rr=mid-1;
	}
	std::cout<<ans<<endl;
	return 0;
}