题解 [HEOI2016/TJOI2016] 排序

题目链接

看到这道题按照套路首先想到二分答案（即二分 \(q\) 位置上的数，记作 \(mid\)）。

再按照套路将大于 \(mid\) 的数字设为 \(1\)，将等于 \(mid\) 的数设为 \(2\)，小于 \(mid\) 的数字设为 \(0\)。

那么对于区间 \([l,r,0]\) 操作，应该先讲 \(0,1,2\) 的数量找出来，然后按照从小到大的顺序 \(0,2,1\) 进行区间赋值，并支持区间求和，这用线段树维护即可。而 \(opt=1\) 的情况也是同理。

现在考虑二分指针如何移动。首先，\(mid,pos\) 两者并不满足单调性，也就是说，\(mid\) 增大，位置不一定取得到后面，减小同理。这时便要从另一个角度思考问题。

如果 \(a_q\) 是 \(1\)，说明答案比当前数字大，我们将指针右移；\(a_q=2\)，说明答案正好是 \(mid\)；\(a_q=0\)，说明答案比当前数字小，将指针左移。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
inline int read() {
    int sum=0,flag=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
    while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
    return sum*flag;
}

const int N=1e5+10;
int n,m,q;
int a[N];
int ql[N],qr[N],qt[N];
int tr[N<<2][3],tag[N<<2][3];
struct node {
    int a0,a1,a2;
    friend node operator + (node x,node y) {
        return {x.a0+y.a0,x.a1+y.a1,x.a2+y.a2};
    }
};

inline void pushup(int nd) {
    for(int i=0;i<=2;i++) tr[nd][i]=tr[nd<<1][i]+tr[nd<<1|1][i];
}

inline void add(int nd,int l,int r,int a0,int a1,int a2) {
    tr[nd][0]=tr[nd][1]=tr[nd][2]=0;
    tag[nd][0]=tag[nd][1]=tag[nd][2]=0;
    if(a0) {tr[nd][0]=r-l+1; tag[nd][0]=1;}
    if(a1) {tr[nd][1]=r-l+1; tag[nd][1]=1;}
    if(a2) {tr[nd][2]=r-l+1; tag[nd][2]=1;}
}

inline void pushdown(int nd,int l,int r) {
    if(!tag[nd][0]&&!tag[nd][1]&&!tag[nd][2]) return ;
    int mid=l+r>>1;
    add(nd<<1,l,mid,tag[nd][0],tag[nd][1],tag[nd][2]);
    add(nd<<1|1,mid+1,r,tag[nd][0],tag[nd][1],tag[nd][2]);
    tag[nd][0]=tag[nd][1]=tag[nd][2]=0;
}

void change(int nd,int l,int r,int x,int y,int a0,int a1,int a2) {
    if(l>y||r<x) return ;
    if(x>y) return ;
    if(l>=x&&r<=y) return add(nd,l,r,a0,a1,a2);
    int mid=l+r>>1;
    pushdown(nd,l,r);
    change(nd<<1,l,mid,x,y,a0,a1,a2);
    change(nd<<1|1,mid+1,r,x,y,a0,a1,a2);
    pushup(nd);
}

node query(int nd,int l,int r,int x,int y) {
    if(l>y||r<x) return {0,0,0};
    if(l>=x&&r<=y) return {tr[nd][0],tr[nd][1],tr[nd][2]};
    int mid=l+r>>1;
    pushdown(nd,l,r);
    return query(nd<<1,l,mid,x,y)+query(nd<<1|1,mid+1,r,x,y);
}

int ask(int nd,int l,int r,int p) {
    if(l==r) {
        if(tr[nd][0]) return 0;
        if(tr[nd][1]) return 1;
        if(tr[nd][2]) return 2;
    }
    int mid=l+r>>1;
    pushdown(nd,l,r);
    if(l<=p&&p<=mid) return ask(nd<<1,l,mid,p);
    else return ask(nd<<1|1,mid+1,r,p);
}

int check(int x) {
    memset(tr,0,sizeof(tr));
    memset(tag,0,sizeof(tag));
    for(int i=1;i<=n;i++) {
        if(a[i]<x) change(1,1,n,i,i,1,0,0);
        if(a[i]==x) change(1,1,n,i,i,0,0,1);
        if(a[i]>x) change(1,1,n,i,i,0,1,0);
    }
    for(int i=1;i<=m;i++) {
        node num=query(1,1,n,ql[i],qr[i]);
        if(qt[i]==0) {
            change(1,1,n,ql[i],ql[i]+num.a0-1,1,0,0);
            change(1,1,n,ql[i]+num.a0,ql[i]+num.a0+num.a2-1,0,0,1);
            change(1,1,n,ql[i]+num.a0+num.a2,qr[i],0,1,0);
        }
        else {
            change(1,1,n,ql[i],ql[i]+num.a1-1,0,1,0);
            change(1,1,n,ql[i]+num.a1,ql[i]+num.a1+num.a2-1,0,0,1);
            change(1,1,n,ql[i]+num.a1+num.a2,qr[i],1,0,0);
        }
    }
    return ask(1,1,n,q);
}

int main() {
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);

    cin>>n>>m;
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++) {
        qt[i]=read();
        ql[i]=read();
        qr[i]=read();
    }
    cin>>q;
    int l=1,r=n;
    while(l<=r) {
        int mid=l+r>>1;
        int k=check(mid);
        if(k==1) l=mid+1;
        if(k==2) {cout<<mid; return 0;}
        if(k==0) r=mid-1;
    }

    return 0;
}