记录编号	433388	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 排序	最终得分	100
用户昵称	yymxw	是否通过	通过
代码语言	C++	运行时间	5.856 s
提交时间	2017-08-05 11:20:25	内存使用	4.99 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
  int x=0,f=1;
  char ch=getchar();
  while(ch<'0'||ch>'9')
  {
    if(ch=='-')
      f=-1;
    ch=getchar();
  }
  while(ch>='0'&&ch<='9')
  {
    x=(x<<3)+(x<<1)+ch-'0';
    ch=getchar();
  }
  return x*f;
}
struct node 
{
  int k,l,r;
};
node q[100010];
int n,m,x,k,y,zuida=0,ying;
int a[100010],add[400010],sum[400010];
bool flag[100010];
void pushup(int i)
{
  sum[i]=sum[2*i]+sum[2*i+1];
  return ;
}
void build(int l,int r,int i)
{
  add[i]=-1;
  if(l==r)
  {
  	sum[i]=flag[l];
    return ;
  }
  int mid=(l+r)>>1;
  build(l,mid,2*i);
  build(mid+1,r,2*i+1);
  pushup(i);
}
void pushdown(int i,int len)
{
  if(add[i]!=-1)
  {
  	add[2*i]=add[i];
  	add[2*i+1]=add[i];
    sum[2*i]=add[i]*(len-len/2);
    sum[2*i+1]=add[i]*len/2;
    add[i]=-1;
  }
}
void update(int L,int R,int c,int l,int r,int i)
{
	if(L>R)  return ;
  if(L<=l&&r<=R)
  {
    add[i]=c;
    sum[i]=c*(r-l+1);
    return ;
  }
  pushdown(i,r-l+1);
  int mid=(l+r)>>1;
  if(L<=mid)
    update(L,R,c,l,mid,2*i);
  if(mid<R)
    update(L,R,c,mid+1,r,2*i+1);
  pushup(i);
}
int query(int L,int R,int l,int r,int i)
{
  if(L<=l&&r<=R)
    return sum[i];
  pushdown(i,r-l+1);
  int mid=(l+r)>>1;
  int ans=0;
  if(L<=mid)
    ans+=query(L,R,l,mid,2*i);
  if(mid<R)
    ans+=query(L,R,mid+1,r,2*i+1);
  return ans;
}
bool check(int x)
{
  for(int i=1;i<=n;++i)
    flag[i]=(a[i]<x);
  build(1,n,1);
  for(int i=1;i<=m;++i)
  {
    int shu=query(q[i].l,q[i].r,1,n,1);
    if(q[i].k==0)
    {
      update(q[i].l,q[i].l+shu-1,1,1,n,1);
      update(q[i].l+shu,q[i].r,0,1,n,1);
    }
    
    if(q[i].k==1)
    { //cout<<53135;
      update(q[i].l,q[i].r-shu,0,1,n,1);
      update(q[i].r-shu+1,q[i].r,1,1,n,1);
    }
  }
  
  if(query(ying,ying,1,n,1)==0)  return 1;
  return 0;
}
int main()
{
	freopen("heoi2016_sort.in","r",stdin);
	freopen("heoi2016_sort.out","w",stdout);
  n=read();m=read();
  build(1,n,1);
  for(int i=1;i<=n;++i)
  {
    a[i]=read();
    if(a[i]>zuida)
      zuida=a[i];
  }
  for(int i=1;i<=m;++i)
  {
    q[i].k=read();q[i].l=read();q[i].r=read();
  }
  int l=0,r=zuida+1,mid;
	ying=read();
  while(l<=r)
  {
  	//memset(flag,0,sizeof(flag));
    mid=(l+r)>>1;
    if(check(mid))
      l=mid+1; 
    else
      r=mid-1;
    //cout<<"l="<<l<<" "<<"r="<<r<<endl;
  }
  printf("%d",r);
  return 0;
}