[HEOI2016/TJOI2016]排序

题目链接

二分+线段树趴

首先让我们想想暴力的做法

emmmmmm

强行暴力，O（n²log₂ⁿ）（直接强行排序）

让我们想想如何优化这个排序，对一个序列排序的时间复杂度是O（nlog₂ⁿ），但是当我们对一个01序列排序的时候就是O（log₂ⁿ）了

那具体怎么做呢？做法如下：

正确做法:

首先二分所求位置数字，将原序列大于mid值的数设为1，小于的设为0

当降序时前半段改为1，后半段改为0

当升序时前半段改为0，后半段改为1

具体改多少个就要通过线段树区间求1个数判断了，若个数为cnt

当降序时[l, r-cnt1]改为1，[l+cnt, r]改为0

当升序时[l, r-cnt1]改为0，[r-cnt1+1, r]改为1

二分验证则判断所求位置是否为1

二分正确性的证明:

这个二分成立因为是满足单调性的：可以简单地假设一下，如果你二分的答案是1，那么原序列所有的值都转化为了1，所以最后肯定是true。如果二分一个值成立当且仅当这个位子的值大于等于mid，故如果check返回true，则l = mid+1，否则r = mid-1。

时间复杂度O（nlog₂n²）

详见代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010; 
int a[maxn],opt[maxn],ll[maxn],rr[maxn];
int n,m;
int hh;
struct SYM{
    int sum;
    int lazy; 
}tree[8*maxn] ;
void build(int i,int l,int r,int x){               //建树
    if(l==r){
        tree[i].sum=(a[l]>=x);
        tree[i].lazy=0;
        return ;
    }
    int mid=(l+r)/2;
    build(2*i,l,mid,x);
    build(2*i+1,mid+1,r,x);
    tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
    tree[i].lazy=0;
}
void pushdown(int i,int l,int r){                  //下传lazy标记
    int mid=(l+r)/2;
    if(!tree[i].lazy) return ;
    tree[2*i].lazy=tree[2*i+1].lazy=tree[i].lazy;
    if(tree[i].lazy==1){
        tree[2*i].sum=(mid-l+1);
        tree[2*i+1].sum=(r-mid); 
    }
    else tree[2*i].sum=tree[2*i+1].sum=0;
    tree[i].lazy=0;
}
void pushup(int i){
    tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
}
int query(int i,int l,int r,int L,int R){                      //查询1个数
    if(l>=L&&r<=R)
        return tree[i].sum;
    if(r<L||l>R) return 0;
    pushdown(i,l,r);
    int mid=(l+r)/2;
    return query(2*i,l,mid,L,R)+query(2*i+1,mid+1,r,L,R);
}
void update(int i,int l,int r,int L,int R,int x){            //更新
    if(l>=L&&r<=R){
        if(x==1){
            tree[i].sum=(r-l+1);
            tree[i].lazy=1;
        }
        else tree[i].sum=0,tree[i].lazy=-1;
        return ;
    }
    if(r<L||l>R) return ;
    pushdown(i,l,r);
    int mid=(l+r)/2;
    update(2*i,l,mid,L,R,x);
    update(2*i+1,mid+1,r,L,R,x);
    pushup(i);
}
int query1(int i,int l,int r,int x){
    if(l==x&&r==x) return tree[i].sum;
    int mid=(l+r)/2;
    pushdown(i,l,r);
    if(x<=mid) query1(2*i,l,mid,x);
    else query1(2*i+1,mid+1,r,x);
}
int check(int x){
    build(1,1,n,x);
    for(int i=1;i<=m;i++){
        int cnt=query(1,1,n,ll[i],rr[i]);
        if(opt[i]==1){
            update(1,1,n,ll[i],ll[i]+cnt-1,1);                  //当降序时[l, r-cnt1]改为1，[l+cnt, r]改为0

            update(1,1,n,ll[i]+cnt,rr[i],0);
        }
        if(opt[i]==0){
            update(1,1,n,rr[i]-cnt+1,rr[i],1);                 //当升序时[l, r-cnt1]改为0，[r-cnt1+1, r]改为1
            update(1,1,n,ll[i],rr[i]-cnt,0);
        }
    }
    return query1(1,1,n,hh);
}
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",&opt[i],&ll[i],&rr[i]);
    scanf("%d",&hh);
    int lll=1,rrr=n,ans;
    while(lll<=rrr){
        int mid=(lll+rrr)/2;
        if(check(mid)) ans=mid,lll=mid+1;
        else rrr=mid-1;
    }
    printf("%d",ans);
    return 0;
}