记录编号	360687	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 排序	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	5.070 s
提交时间	2016-12-31 08:28:26	内存使用	4.87 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100010;
void build(int,int,int);
void modify(int,int,int);
void qsum(int,int,int);
void pushdown(int,int,int,int);
int sm[maxn<<2],lazy[maxn<<2];
int n,m,a[maxn],l[maxn],r[maxn],rev[maxn],q,s,t,d,tmp,L,R,M;
int main(){
	freopen("heoi2016_sort.in","r",stdin);
	freopen("heoi2016_sort.out","w",stdout);
	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",&rev[i],&l[i],&r[i]);
	scanf("%d",&q);
	L=1;R=n;
	while(L<=R){
		M=(L+R)>>1;
		build(1,n,1);
		for(int i=1;i<=m;i++){
			s=l[i];t=r[i];tmp=0;
			qsum(1,n,1);
			if(rev[i]){
				if(tmp){
					s=l[i];t=l[i]+tmp-1;d=1;
					modify(1,n,1);
				}
				if(tmp!=r[i]-l[i]+1){
					s=l[i]+tmp;t=r[i];d=0;
					modify(1,n,1);
				}
			}
			else{
				tmp=r[i]-l[i]-tmp+1;
				if(tmp){
					s=l[i];t=l[i]+tmp-1;d=0;
					modify(1,n,1);
				}
				if(tmp!=r[i]-l[i]+1){
					s=l[i]+tmp;t=r[i];d=1;
					modify(1,n,1);
				}
			}
		}
		s=t=q;tmp=0;
		qsum(1,n,1);
		if(tmp)L=M+1;
		else R=M-1;
	}
	printf("%d",R);
	return 0;
}
void build(int l,int r,int rt){
	lazy[rt]=-1;
	if(l==r){
		sm[rt]=(a[l]>=M);
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	sm[rt]=sm[rt<<1]+sm[rt<<1|1];
}
void modify(int l,int r,int rt){
	if(s<=l&&t>=r){
		sm[rt]=d*(r-l+1);
		lazy[rt]=d;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(l,r,mid,rt);
	if(s<=mid)modify(l,mid,rt<<1);
	if(t>mid)modify(mid+1,r,rt<<1|1);
	sm[rt]=sm[rt<<1]+sm[rt<<1|1];
}
void qsum(int l,int r,int rt){
	if(s<=l&&t>=r){
		tmp+=sm[rt];
		return;
	}
	int mid=(l+r)>>1;
	pushdown(l,r,mid,rt);
	if(s<=mid)qsum(l,mid,rt<<1);
	if(t>mid)qsum(mid+1,r,rt<<1|1);
}
void pushdown(int l,int r,int mid,int rt){
	if(lazy[rt]==-1)return;
	sm[rt<<1]=lazy[rt]*(mid-l+1);
	sm[rt<<1|1]=lazy[rt]*(r-mid);
	lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
	lazy[rt]=-1;
}