记录编号	427735	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 排序	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	5.674 s
提交时间	2017-07-23 07:23:05	内存使用	5.25 MiB

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
int Judge,a[MAXN],n,m,p,Ans;


template<typename _t>
inline _t read(){
    _t x=0;
    int f=1;
    char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+(ch^48);
    return x*f;
}

struct node{
    node *ls,*rs;
    int sum,set,l,r;

    inline int __ls(){return ls?ls->sum:0;}
    inline int __rs(){return rs?rs->sum:0;}

    void Maintain(){
        sum=__ls()+__rs();
    }

    void push_down(){
        if(set==-1)return;
        int m=l+r>>1;
        if(ls){
            ls->set=set;
            ls->sum=(m-l+1)*set;
        }
        if(rs){
            rs->set=set;
            rs->sum=(r-m)*set;
        }
        set=-1;
    }

    node(){
        ls=rs=NULL;
        sum=0;set=-1;
    }
}*root;

void build(node *&o,int l,int r){
    if(!o)o=new node();
    o->l=l;o->r=r;
    o->set=-1;
    if(l==r){
        o->sum=(a[l]>=Judge);
        return;
    }
    int m=l+r>>1;
    build(o->ls,l,m);
    build(o->rs,m+1,r);
    o->Maintain();
}

void Update(node *o,int l,int r,int val){
    if(l>r)return;
    o->push_down();
    if(l<=o->l&&o->r<=r){
        o->set=val;
        o->sum=val*(o->r-o->l+1);
        return;
    }
    int m=o->l+o->r>>1;
    if(l<=m)Update(o->ls,l,r,val);
    if(m<r)Update(o->rs,l,r,val);
    o->Maintain();
}

int Query(node *o,int l,int r){
    o->push_down();
    if(l<=o->l&&o->r<=r)return o->sum;
    int m=o->l+o->r>>1,ans=0;
    if(l<=m)ans+=Query(o->ls,l,r);
    if(m<r)ans+=Query(o->rs,l,r);
    return ans;
}

struct Operation{
    int op,l,r;
    void init(){
        op=read<int>();
        l=read<int>();
        r=read<int>();
    }
}c[MAXN];

int main(){
    freopen("heoi2016_sort.in","r",stdin);
    freopen("heoi2016_sort.out","w",stdout);
    n=read<int>();m=read<int>();
    int maxn = -0x3f3f3f3f;
    for(int i=1;i<=n;i++)a[i]=read<int>(),maxn=max(maxn,a[i]);
    for(int i=1;i<=m;i++)c[i].init();
    p=read<int>();
    int l=1,r=maxn;
    while(l<=r){
        Judge=l+r>>1;
        build(root,1,n);
        for(int i=1;i<=m;i++){
            if(c[i].op==0){
                int sum = Query(root,c[i].l,c[i].r);
                Update(root,c[i].r-sum+1,c[i].r,1);
                Update(root,c[i].l,c[i].r-sum,0);
            }
            else{
                int sum = Query(root,c[i].l,c[i].r);
                Update(root,c[i].l+sum,c[i].r,0);
                Update(root,c[i].l,c[i].l+sum-1,1);
            }
        }
        int ans = Query(root,p,p);
        if(ans)Ans=Judge,l=Judge+1;
        else r=Judge-1;
    }
    printf("%d\n",Ans);
}