HDU 5649 DZY Love Sorting 题解(二分套线段树)

题目链接

题目大意

有一个数组 (a)，它是一个长度为(n(nle1e5))的全排列。

现在他想执行多次下列两种操做：

• (0;l;r)表示对(a[l..r])进行升序排序
• (1; l; r)表示对 (a[l..r]) 进行降序排序

问经过 (m(mle1e5))次操作后(a[k])为多少？

题目思路

这个题目挺难的

直接模拟题意显然会(TLE)

因为我们最终只要求一个元素，考虑二分答案(x)

那么排列中大于等于(x)的数全都设为(1),小于(x)的数都设为 (0)

若为升序排序

现在区间排序，只要把区间里的(0)都移到最前面， (1)都移到最后面。

对于区间([l, r])查询([l, r])的子段和(sum)。

然后将([l, r - sum])修改为 (0)，([r - sum + 1, r])修改为(1).

反之亦然

这个题目主要是考虑相对大小

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,m,k;
int a[maxn];
int tree[maxn<<2],lazy[maxn<<2];
int opt[maxn],l[maxn],r[maxn];
void build(int node,int l,int r,int x){
    lazy[node]=-1;
    if(l==r){
        tree[node]=(a[l]>=x);
        return ;
    }
    int mid=(l+r)/2;
    build(node<<1,l,mid,x);
    build(node<<1|1,mid+1,r,x);
    tree[node]=tree[node<<1]+tree[node<<1|1];
}

void updown(int node,int l,int r){
    if(lazy[node]!=-1){
        int mid=(l+r)/2;
        lazy[node<<1]=lazy[node];
        lazy[node<<1|1]=lazy[node];
        tree[node<<1]=(mid-l+1)*lazy[node];
        tree[node<<1|1]=(r-mid)*lazy[node];
        lazy[node]=-1;
    }
}
void update(int node,int L,int R,int l,int r,int add){
    if(L<=l&&r<=R){
        tree[node]=(r-l+1)*add;
        lazy[node]=add;
        return ;
    }
    updown(node,l,r);
    int mid=(l+r)/2;
    if(mid>=L) update(node<<1,L,R,l,mid,add);
    if(mid<R)  update(node<<1|1,L,R,mid+1,r,add);
    tree[node]=tree[node<<1]+tree[node<<1|1];
}
int query(int node,int L,int R,int l,int r){
    if(L<=l&&r<=R){
        return tree[node];
    }
    updown(node,l,r);
    int mid=(l+r)/2,sum=0;
    if(mid>=L) sum+=query(node<<1,L,R,l,mid);
    if(mid<R)  sum+=query(node<<1|1,L,R,mid+1,r);
    return sum;
}

bool check(int x){
    build(1,1,n,x);
    for(int i=1;i<=m;i++){
        int sum=query(1,l[i],r[i],1,n);
        if(opt[i]==0){
            if(r[i]-sum>=l[i])  update(1,l[i],r[i]-sum,1,n,0);
            if(r[i]>=r[i]-sum+1) update(1,r[i]-sum+1,r[i],1,n,1);
        }else{
            if(l[i]+sum-1>=l[i])  update(1,l[i],l[i]+sum-1,1,n,1);
            if(r[i]>=l[i]+sum) update(1,l[i]+sum,r[i],1,n,0);
        }
    }
    return query(1,k,k,1,n);
}
signed main(){
    int _;scanf("%d",&_);
    while(_--){
        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],&l[i],&r[i]);
        }
        scanf("%d",&k);
        int l=1,r=n,ans=-1;
        while(l<=r){
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        printf("%d
",ans);
    }
    return 0;
}