记录编号	359193	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 排序	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	9.204 s
提交时间	2016-12-21 09:34:46	内存使用	10.91 MiB

#include<cstdio>
const int N=5e5+10;
int n,m,q,a[N],l[N],r[N],tp[N];
#define lc x<<1
#define rc (x<<1)|1
int sum[N],tag[N],k[N];
void update(int x){
	sum[x]=sum[lc]+sum[rc];
}
void pushdown(int x,int l,int r){
	if (l!=r&&tag[x]!=-1){
		int mid=(l+r)>>1;
		tag[lc]=tag[rc]=tag[x];
		sum[lc]=(mid-l+1)*tag[x];
		sum[rc]=(r-mid)*tag[x];
		tag[x]=-1;
	}
}
void clear(int x,int l,int r){
	tag[x]=-1;
	if (l==r){sum[x]=k[l];return;}
	int mid=(l+r)>>1;
	clear(lc,l,mid);
	clear(rc,mid+1,r);
	update(x);
}
void change(int x,int l,int r,int L,int R,int d){
	pushdown(x,l,r);
	if (l>=L&&r<=R){
		tag[x]=d;sum[x]=(r-l+1)*d;
		return;
	}
	int mid=(l+r)>>1;
	if (R>mid) change(rc,mid+1,r,L,R,d);
	if (L<=mid) change(lc,l,mid,L,R,d);
	update(x);
}
int getsum(int x,int l,int r,int L,int R){
	pushdown(x,l,r);
	if (l>=L&&r<=R) return sum[x];
	int mid=(l+r)>>1,ans=0;
	if (R>mid) ans+=getsum(rc,mid+1,r,L,R);
	if (L<=mid) ans+=getsum(lc,l,mid,L,R);
	update(x);
	return ans;
}
void A(){
	
}
int erfen(int L,int R){
	if (L==R) return L;
	int mid=(L+R)>>1;
	for (int i=1;i<=n;i++) k[i]=a[i]>mid;
	clear(1,1,n);
	for (int i=1;i<=m;i++){
		if (i==61) A();
		int x=getsum(1,1,n,l[i],r[i]);
		change(1,1,n,l[i],r[i],0);
		if (x&&tp[i]) change(1,1,n,l[i],l[i]+x-1,1);
			else change(1,1,n,r[i]-x+1,r[i],1);
	}
	int ans=getsum(1,1,n,q,q);
	return ans?erfen(mid+1,R):erfen(L,mid); 
}
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",&tp[i],&l[i],&r[i]);
	scanf("%d",&q);
	printf("%d\n",erfen(1,n));
	return 0;
}