记录编号	599882	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 排序	最终得分	100
用户昵称	秋_Water	是否通过	通过
代码语言	C++	运行时间	5.783 s
提交时间	2025-03-29 22:51:15	内存使用	14.98 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct node{
	int l,r,sum1;
	int col;
}t[4*N];
int a[N],ql[N],qr[N],qop[N],cnt,n,m,ans,q;
void pushdown(int k,int l,int r){
	if(t[k].col!=0){
		t[t[k].l].col=t[t[k].r].col=t[k].col;
		if(t[k].col==1){
			int mid=l+r>>1;
			t[t[k].l].sum1=mid-l+1;
			t[t[k].r].sum1=r-mid;
		}
		else{
			t[t[k].l].sum1=0;
			t[t[k].r].sum1=0;			
		}
		t[k].col=0;
	}	
}
void build(int &p,int l,int r,int k){
	p=++cnt;
	if(l==r){
		t[p].sum1=(a[l]>=k);
		t[p].col=0;
		return;
	}
	int mid=l+r>>1;
	build(t[p].l,l,mid,k);
	build(t[p].r,mid+1,r,k);
	t[p].sum1=t[t[p].l].sum1+t[t[p].r].sum1;
	t[p].col=0;
} 
int query(int p,int l,int r,int ql,int qr){
	if(ql<=l&&qr>=r){
		return t[p].sum1;
	}
	if(ql>r||qr<l) return 0;
	if(l>r){
		return 0;
	} 
	pushdown(p,l,r);
	int mid=l+r>>1;
	return query(t[p].l,l,mid,ql,qr)+query(t[p].r,mid+1,r,ql,qr);
}
void moditf(int k,int ql,int qr,int l,int r,int val){
    if (ql>r||qr<l) return;    
    if(ql<=l&&qr>=r){
    	t[k].sum1=(r-l+1)*val;
		if(val==1) t[k].col=1;
		else{
			t[k].col=-1;
		}
        return;
    }	
	pushdown(k,l,r);
    int mid=l+r>>1;
    moditf(t[k].l,ql,qr,l,mid,val);
    moditf(t[k].r,ql,qr,mid+1,r,val);
    t[k].sum1=t[t[k].l].sum1+t[t[k].r].sum1;
}
bool cheak(int x){
	int root=0;
	build(root,1,n,x);
	for(int i=1;i<=m;i++){
		int tot=query(root,1,n,ql[i],qr[i]);
		if(qop[i]==0){
			moditf(root,qr[i]-tot+1,qr[i],1,n,1);
			moditf(root,ql[i],qr[i]-tot,1,n,0);
		}
		else{
			moditf(root,ql[i],ql[i]+tot-1,1,n,1);
			moditf(root,ql[i]+tot,qr[i],1,n,0);			
		}
	}
	return query(root,1,n,q,q);
}
int main(){
	freopen("heoi2016_sort.in","r",stdin);
	freopen("heoi2016_sort.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>qop[i]>>ql[i]>>qr[i];
	}
	cin>>q;
	int l=1,r=n,mid;
	while(l<=r){
		mid=l+r>>1;
		if(cheak(mid)){
			ans=mid;
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	cout<<ans;

	return 0;
}