3130ソート

Taskは1−nの全配列を与え,m回の操作は2種類に分けられる:①(0,l,r)区間[l,r]を昇順に②( 1,l,r)区間[l,r]を降順に配列する.n,m<=1e5
Solution 6秒の時限は、本当に暴力的な良いタイミングでsort関数sort(A+l,A+r+1,cmp)で区間[l,r]を昇順または降順に並べることができ、80分になります.しかし本人は下品で、sort(A+l+1,A+r+1)と書いてありますが、意外にも60分も普段のsortが(A,A+n)か(A+1,A+n+1)で、それぞれ左端点、右端点+1の位置だと思います.
「二分は一つの方向」二分の利点:知識を求める問題を判定問題に変換する.類似のテーマ:区間第k値、中位数.
二分xは、解がx以上であるか否かを判定する.xに従って、x以上の数を1とし、x未満の数を0とする.m回操作後、idビット上の数が1であれば実行可能と判定する.
問題は、1つの01シーケンス、m回の操作後、idビットの数が1であるかどうかに変換される.1区間が01しかないため,昇順降順にかかわらず0と1の境界点が1つある.区間の長さが一定であるため,区間の和を求めると,1の個数を見つけることができる.②境界線の前部分をc、後部分をc^1とする.(cは0または1)である.
区間加算、区間更新は、遅延更新のセグメントツリーで完了できます.

const int M=1e5+3;
int A[M];
int n,m,pos;
struct node1{
    int cnt[2],l,r,f;
    inline void clear(){
        memset(cnt,0,sizeof(cnt));
    }
}res;
struct node2{
    int a,l,r;
}Q[M];
struct Segment_Tree{
    node1 t[M<<2];
    inline void up(int p){
        rep(i,0,1)
            t[p].cnt[i]=t[lsn(p)].cnt[i]+t[rsn(p)].cnt[i];
    }
    inline void down(int p){
        if(t[p].f==-1)return;
        int c=t[p].f,l=lsn(p),r=rsn(p);
        t[l].f=t[r].f=c;
        t[l].cnt[c]=t[l].r-t[l].l+1;
        t[r].cnt[c]=t[r].r-t[r].l+1;
        t[l].cnt[c^1]=t[r].cnt[c^1]=0;
        t[p].f=-1;
    }
    inline void build(int l,int r,int x,int p){
        t[p].l=l,t[p].r=r;t[p].f=-1;
        if(l==r){
            bool a=(A[l]>=x);
            t[p].cnt[a]=1;t[p].cnt[a^1]=0;
            return;
        }
        int mid=l+r>>1;
        build(l,mid,x,lsn(p));
        build(mid+1,r,x,rsn(p));
        up(p);
    }
    inline void query(int L,int R,int l,int r,int p){
        if(l==L&&r==R){
            rep(i,0,1)res.cnt[i]+=t[p].cnt[i];
            return;
        }
        down(p);
        int mid=L+R>>1;
        if(r<=mid)query(L,mid,l,r,lsn(p));
        else if(l>mid)query(mid+1,R,l,r,rsn(p));
        else{
            query(L,mid,l,mid,lsn(p));
            query(mid+1,R,mid+1,r,rsn(p));
        }
    }
    inline void update(int L,int R,int l,int r,int c,int p){// c  
        if(l==L&&r==R){
            t[p].cnt[c]=r-l+1;
            t[p].cnt[c^1]=0;
            t[p].f=c;
            return;
        }
        down(p);
        int mid=L+R>>1;
        if(r<=mid)update(L,mid,l,r,c,lsn(p));
        else if(l>mid)update(mid+1,R,l,r,c,rsn(p));
        else{
            update(L,mid,l,mid,c,lsn(p));
            update(mid+1,R,mid+1,r,c,rsn(p));
        }
        up(p);
    }
}T;
struct P100{
    inline void input(){
        rd(n);rd(m);
        rep(i,1,n)rd(A[i]);
        rep(i,1,m){
            rd(Q[i].a);rd(Q[i].l);rd(Q[i].r);
        }
        rd(pos);
    }
    inline bool check(int x){// >=x 
        int a,l,r;
        T.build(1,n,x,1);
        rep(i,1,m){
            res.clear();
            a=Q[i].a,l=Q[i].l,r=Q[i].r;
            T.query(1,n,l,r,1);
            if(min(res.cnt[0],res.cnt[1])==0)continue;// 0 1 
            T.update(1,n,l,l+res.cnt[a]-1,a,1);// a
            T.update(1,n,l+res.cnt[a],r,a^1,1);// a^1 
        }
        res.clear();
        T.query(1,n,pos,pos,1);
        return res.cnt[1]==1;

    }
    inline void solve(){
        input();
        int l=1,r=n,mid,ans;
        while(l<=r){
            mid=l+r>>1;
            if(check(mid)){l=mid+1;ans=mid;}
            else r=mid-1;
        }
        sc(ans);
    }
}P100;
int main(){
    P100.solve();
    return 0;
}