<h2>题目描述</h2>

题目链接

对一个长度为 $n$ 的排列进行 $m$ 次如下操作：

1. 将区间 $[l,r]$ 中的数字升序排序。
2. 将区间 $[l,r]$ 中的数字降序排序

最后输出位置 $p$ 的数字。

其中 $1 \leq n,m \leq 10^5$

<h2>解题报告</h2>

发现询问只有一组，我们可以考虑二分答案。

考虑二分答案 $p$ 表示该输出的答案。因为这是一个排列，所以我们可以把小于 $p$ 的数标记为 $0$ ，大于 $p$ 的数标记为 $1$ ，线段树维护一下区间覆盖和求和，最后检验一下位置是 $0$ 还是 $1$ 就可以了。

升序排序相当于把 $1$ 放到后边，降序排序则是放到前边。

如果二分后位置是 $0$ 的话显然正确答案比二分的答案要更大，是 $1$ 的话则要小，因为二分成立当且仅当这个位置的数是 $1$。

#include <iostream>
#include <cstring>
#include <cstdio>
#define FOR(i,a,b) for(register int i = a;i <= b;++i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100000 + 5;

struct SegmentTree New(int ,int ,SegmentTree ,SegmentTree *);

struct SegmentTree{
    int l,r,sum,tag;
    SegmentTree lc,rc;
    
    static SegmentTree *build(int l,int r){
        int mid = (l + r) >> 1;
        return (l == r) ? New(l,r,NULL,NULL) : New(l,r,build(l,mid),build(mid+1,r));
    }
    
    inline void pushup(){
        sum = lc->sum + rc->sum; 
    }
    
    inline void cover(int delta){
        sum = (r-l+1)*delta;
        tag = delta;
    }
    
    inline void pushdown(){
        if(tag != -1){
            lc->cover(tag);
            rc->cover(tag);
            tag = -1;
        }
    }
    
    void modify(int L,int R,int x){
        if(L == l && R == r){
            cover(x);
            return;
        }
        pushdown();
        int mid = (l + r) >> 1;
        if(R <= mid) lc->modify(L,R,x);
        else if(L > mid) rc->modify(L,R,x);
        else lc->modify(L,mid,x),rc->modify(mid+1,R,x);
        pushup();
    }
    
    int query(int L,int R){
        if(L == l && R == r) return sum;
        pushdown();
        int mid = (l + r) >> 1;
        if(R <= mid) return lc->query(L,R);
        else if(L > mid) return rc->query(L,R);
        return lc->query(L,mid) + rc->query(mid+1,R);
    }
}pool[MAXN<<2],frog = pool,segt;

SegmentTree New(int l,int r,SegmentTree lc,SegmentTree *rc){
    SegmentTree *ret = ++frog;
    ret->l = l;ret->r = r;
    ret->lc = lc;ret->rc = rc;
    ret->sum = 0;ret->tag = -1;
    return ret;
}

int N,M;
int a[MAXN],pos;

struct Data{
    int l,r,opt;
}d[MAXN];

inline bool check(int k){ // Answer_pos >= k_pos ? 
    FOR(i,1,N) segt->modify(i,i,(a[i] >= k) ? 1 : 0);
    FOR(i,1,M){
        int l = d[i].l,r = d[i].r,opt = d[i].opt;
        int t = segt->query(d[i].l,d[i].r); // 1
        // printf("%d %d %d %dn",l,r,opt,t);
        //DEBUG(l);DEBUG(r);DEBUG(t);
        if(opt){
            if(l <= l+t-1) segt->modify(l,l+t-1,1);
            if(l+t <= r) segt->modify(l+t,r,0);
            
            // [l,l+t-1]:1 [l+t,r]:0
        }
        else{ // 31 37 1 7
            if(l <= r-t) segt->modify(l,r-t,0);
            if(r-t+1 <= r) segt->modify(r-t+1,r,1);
            // [l,r-t]:0 [r-t+1,r]:1
        }
    }
    int ans = segt->query(pos,pos);
    return ans == 1;
}

int main(){
    scanf("%d%d",&N,&M);
    segt = SegmentTree::build(1,N);
    FOR(i,1,N) scanf("%d",a+i);
    FOR(i,1,M) scanf("%d%d%d",&d[i].opt,&d[i].l,&d[i].r);
    scanf("%d",&pos);
    int l = 1,r = N,ans;
    while(l <= r){
        // DEBUG(l);DEBUG(r);
        int mid = (l + r) >> 1;
        if(check(mid)) l = mid+1,ans = mid;
        else r = mid - 1;
    }
    printf("%dn",ans);
    return 0;
}