记录编号	301198	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 排序	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	10.058 s
提交时间	2016-08-30 17:15:00	内存使用	4.38 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lch l,mid,rt<<1
#define rch mid+1,r,rt<<1|1
using namespace std;
const int maxn=100010;
void build(int,int,int);
void mset(int,int,int);
void qsum(int,int,int);
void pushdown(int,int,int,int);
int n,m,p,b[maxn],L[maxn],R[maxn],Rev[maxn],l,r,ans,a[maxn<<2],lazy[maxn<<2],s,t,x,out;
int main(){
#define MINE
#ifdef MINE
	freopen("heoi2016_sort.in","r",stdin);
	freopen("heoi2016_sort.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	for(int i=1;i<=m;i++)scanf("%d%d%d",&Rev[i],&L[i],&R[i]);
	scanf("%d",&p);
	l=1;
	r=n;
	while(l<=r){
		ans=(l+r)>>1;
		//printf("---ans=%d---\n",ans);
		memset(lazy,-1,sizeof(lazy));
		build(1,n,1);
		//printf("\n");
		for(int i=1;i<=m;i++){
			out=0;
			s=L[i];
			t=R[i];
			qsum(1,n,1);
			//printf("i=%d out=%d\n",i,out);
			if(!Rev[i]){
				out=R[i]-L[i]+1-out;
				if(out){
					t=L[i]+out-1;
					x=0;
					//printf("s=%d t=%d x=%d\n",s,t,x);
					mset(1,n,1);
				}
				if(out!=R[i]-L[i]+1){
					s=t+1;
					t=R[i];
					x=1;
					//printf("s=%d t=%d x=%d\n",s,t,x);
					mset(1,n,1);
				}
			}
			else{
				if(out){
					t=L[i]+out-1;
					x=1;
					//printf("s=%d t=%d x=%d\n",s,t,x);
					mset(1,n,1);
				}
				if(out!=R[i]-L[i]+1){
					s=t+1;
					t=R[i];
					x=0;
					//printf("s=%d t=%d x=%d\n",s,t,x);
					mset(1,n,1);
				}
			}
		}
		out=0;
		s=t=p;
		qsum(1,n,1);
		//printf("%d\n",out);
		if(out)l=ans+1;
		else r=ans-1;
	}
	printf("%d",r);
#ifdef MINE
	fclose(stdin);
	fclose(stdout);
#else
	printf("\n--------------------DONE--------------------\n");
	for(;;);
#endif
	return 0;
}
void build(int l,int r,int rt){
	if(l==r){
		a[rt]=b[l]>=ans;
		//printf("%d ",a[rt]);
		return;
	}
	int mid=(l+r)>>1;
	build(lch);
	build(rch);
	a[rt]=a[rt<<1]+a[rt<<1|1];
}
void mset(int l,int r,int rt){
	if(s<=l&&t>=r){
		a[rt]=x*(r-l+1);
		lazy[rt]=x;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(l,r,mid,rt);
	if(s<=mid)mset(lch);
	if(t>mid)mset(rch);
	a[rt]=a[rt<<1]+a[rt<<1|1];
}
void qsum(int l,int r,int rt){
	if(s<=l&&t>=r){
		out+=a[rt];
		return;
	}
	int mid=(l+r)>>1;
	pushdown(l,r,mid,rt);
	if(s<=mid)qsum(lch);
	if(t>mid)qsum(rch);
}
void pushdown(int l,int r,int mid,int rt){
	if(lazy[rt]==-1)return;
	int lc=rt<<1,rc=lc|1;
	lazy[lc]=lazy[rc]=lazy[rt];
	a[lc]=lazy[rt]*(mid-l+1);
	a[rc]=lazy[rt]*(r-mid);
	lazy[rt]=-1;
}