luoguP2824 [HEOI2016/TJOI2016]排序 二分+线段树

题意：给定一个排列，每次有两种操作：1 区间降序排列 2 区间升序排列，求 m 才操作后 q 位置上的数字

这道题非常神仙啊.    

假如说序列中只有 0，1 的话我们只需要用线段树维护 0，1的个数然后进行区间覆盖即可.     

由于所有数互不相同，考虑二分 $q$ 点上的数 $mid$，然后将大于等于 $mid$ 的设置成 $1$，小于的设置成 $0$.    

然后我们对新构建的序列从头到尾操作一下，发现如果 $q$ 位置是 $1$ 的话答案要大于等于 $mid$，反之亦然.       

那么这个 $q$ 点的答案就满足单调性了，可以二分.   

总时间复杂度为 $O(n log^2 n)$   

code: 

#include <bits/stdc++.h>     
#define N 100009    
#define lson now<<1
#define rson now<<1|1
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;       
int n,as,m; 
int a[N],b[N];  
int c[2][N<<2],t[2][N<<2],len[N<<2];  
struct data {  
    int l,r,op;
}p[N];     
void pushup(int now)  {  
    c[0][now]=c[0][lson]+c[0][rson];  
    c[1][now]=c[1][lson]+c[1][rson];   
}   
void mark(int now,int v) {    
    t[v][now]=1,t[v^1][now]=0;       
    c[v][now]=len[now],c[v^1][now]=0;    
}
void pushdown(int now) {  
    if(t[0][now]) mark(lson,0),mark(rson,0),t[0][now]=0;  
    if(t[1][now]) mark(lson,1),mark(rson,1),t[1][now]=0;       
}
void build(int l,int r,int now) {    
    c[0][now]=c[1][now]=0; 
    t[0][now]=t[1][now]=0;  
    len[now]=r-l+1;   
    if(l==r) {     
        c[b[l]][now]=1;  
        return;  
    }  
    int mid=(l+r)>>1;  
    build(l,mid,lson),build(mid+1,r,rson); 
    pushup(now); 
}
int query(int l,int r,int now,int L,int R,int v) {  
    if(l>=L&&r<=R) return c[v][now];  
    int mid=(l+r)>>1,re=0; 
    pushdown(now);  
    if(L<=mid)  re+=query(l,mid,lson,L,R,v);  
    if(R>mid)   re+=query(mid+1,r,rson,L,R,v);  
    return re;   
}
void upd(int l,int r,int now,int L,int R,int v) {   
    if(l>=L&&r<=R) { mark(now,v); return; }  
    int mid=(l+r)>>1;  
    pushdown(now);  
    if(L<=mid)   upd(l,mid,lson,L,R,v);  
    if(R>mid)    upd(mid+1,r,rson,L,R,v);      
    pushup(now);   
}
int check(int tmp) {        
    for(int i=1;i<=n;++i) b[i]=(a[i]>=tmp);   
    build(1,n,1);    
    int l,r,op,x,y,z;  
    for(int i=1;i<=m;++i) {   
        l=p[i].l,r=p[i].r,op=p[i].op;  
        if(op==0) {  
            x=query(1,n,1,l,r,0);  
            y=query(1,n,1,l,r,1);        
            if(x) upd(1,n,1,l,l+x-1,0);   
            if(y) upd(1,n,1,r-y+1,r,1);    
        } 
        else { 
            x=query(1,n,1,l,r,0);  
            y=query(1,n,1,l,r,1);  
            if(y) upd(1,n,1,l,l+y-1,1);   
            if(x) upd(1,n,1,r-x+1,r,0);   
        }
    }
    return query(1,n,1,as,as,1);     
}
int main() {  
    // setIO("input");     
    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",&p[i].op,&p[i].l,&p[i].r);          
    }    
    scanf("%d",&as);   
    int l=1,r=n,ans=0,mid; 
    while(l<=r) {  
        mid=(l+r)>>1;  
        if(check(mid))  ans=mid,l=mid+1;  
        else r=mid-1;        
    }
    printf("%d
",ans);  
    return 0; 
}