题面

分析

此题是道好题！

首先要跳出思维定势，不是去想如何用数据结构去直接维护排序过程，而是尝试二分a[p]的值

设二分a[p]的值为x

我们将大于x的数标记为1，小于等于x的数标记为0

则整个序列只由01组成,记为b

将一个区间升序排序，则相当于将1全部移到右边,0全部移到左边，降序排序反之

例：

a={1,6,5,2,4,3}.x=4

标记后的序列b为{0,1,1,0,0,0}

此时对[1,5]进行升序排序,a={1,2,4,5,6,3}

标记后的序列b为{0,0,0,1,1,0}

因此可以用线段树维护标记后的序列，直接区间求和得到1的个数，再区间更新即可

如果排完序后b[p]=0,则说明a[p]<=x,继续减小x

否则增大x

代码

#include
    
     #include
     
      #include
      
       #include
       
        #define maxn 100005using namespace std;int n,m,qa;struct node {    int l;    int r;    int v;    int mark;    int len() {        return r-l+1;    }} tree[maxn<<2];int a[maxn];struct sort_seg {    int l;    int r;    int type;} q[maxn];void push_up(int pos) {    tree[pos].v=tree[pos<<1].v+tree[pos<<1|1].v;}void build(int l,int r,int pos,int middle) {    tree[pos].l=l;    tree[pos].r=r;    tree[pos].v=0;    tree[pos].mark=-1;    if(l==r) {        tree[pos].v=(a[l]>middle);        return;    }    int mid=(tree[pos].l+tree[pos].r)>>1;    build(l,mid,pos<<1,middle);    build(mid+1,r,pos<<1|1, middle);    push_up(pos);}void push_down(int pos) {    if(tree[pos].mark!=-1) {        tree[pos<<1].mark=tree[pos].mark;        tree[pos<<1|1].mark=tree[pos].mark;        tree[pos<<1].v=tree[pos].mark*tree[pos<<1].len();        tree[pos<<1|1].v=tree[pos].mark*tree[pos<<1|1].len();        tree[pos].mark=-1;    }}void update(int L,int R,int v,int pos) {    if(R
        
         tree[pos].r) return;    if(L<=tree[pos].l&&R>=tree[pos].r) {        tree[pos].v=v*tree[pos].len();        tree[pos].mark=v;        return;    }    push_down(pos);    int mid=(tree[pos].l+tree[pos].r)>>1;    if(L<=mid) update(L,R,v,pos<<1);    if(R>mid) update(L,R,v,pos<<1|1);    push_up(pos);}int query(int L,int R,int pos) {    if(R
         
          tree[pos].r) return 0; if(L<=tree[pos].l&&R>=tree[pos].r) { return tree[pos].v; } push_down(pos); int mid=(tree[pos].l+tree[pos].r)>>1; int ans=0; if(L<=mid) ans+=query(L,R,pos<<1); if(R>mid) ans+=query(L,R,pos<<1|1); return ans;}int check(int x) { build(1,n,1,x); for(int i=1; i<=m; i++) { int sum=query(q[i].l,q[i].r,1); if(q[i].type==0) { update(q[i].l,q[i].r-sum,0,1); update(q[i].r-sum+1,q[i].r,1,1); } else { update(q[i].l,q[i].l+sum-1,1,1); update(q[i].l+sum,q[i].r,0,1); } } if(query(qa,qa,1)==1) return 0; else return 1;}int main() { 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",&q[i].type,&q[i].l,&q[i].r); } int l=1,r=n; int ans=n+1; scanf("%d",&qa); while(l<=r) { int mid=(l+r)>>1; if(check(mid)) { ans=min(ans,mid); r=mid-1; } else { l=mid+1; } } printf("%d\n",ans);}