题解 P2824 [TJOI2016]排序

题解-P2824[HEOI2016/TJOI2016]排序

• 题目意思

就是给你一个排列，接下来有次操作每次将区间里的数降序或者升序排列，最后询问。

这道题目主要是思想的转化，其他并无难点。对于这种思想的转化可以看戳这里。

考虑离线。

我们可以二分答案，对于每次二分的答案如果大于那么将变为否则变为。

然后对于修改为递增序列我们可以先统计出区间中的个数，然后将区间里的数变为
并且将里的数变为,如果是递减序列也是相近类似的操作。这些都是可以用线段树进行维护的。

对于最后我们只要判断是不是为即可。

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

const int maxn=1e5+5;
const int maxm=4e5+5;

int n,m,op[maxn],val[maxn],ans;
int tr[maxm],tag[maxm],Q;

struct number {
    int opt,l,r;
};
number q[maxn];

inline int read() {
    int sum=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) 
        sum=sum*10+(ch^48),ch=getchar();
    return sum;
}

inline void build(int rt,int l,int r) {
    tag[rt]=-1;
    if(l==r) {
        tr[rt]=op[l];
        return;
    }
    int mid=(l+r)/2;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}

inline void push_down(int rt,int l,int r) {
    if(tag[rt]==-1) return;
    int mid=(l+r)/2;
    tr[rt<<1]=(mid-l+1)*tag[rt];
    tr[rt<<1|1]=(r-mid)*tag[rt];
    tag[rt<<1]=tag[rt];
    tag[rt<<1|1]=tag[rt];
    tag[rt]=-1;
}

inline void modify(int rt,int l,int r,int ll,int rr,int val) {
    if(l>rr||r<ll) return;
    if(ll<=l&&r<=rr) {
        tr[rt]=val*(r-l+1);
        tag[rt]=val;
        return;
    }
    push_down(rt,l,r);
    int mid=(l+r)/2;
    if(ll<=mid) modify(rt<<1,l,mid,ll,rr,val);
    if(rr>mid) modify(rt<<1|1,mid+1,r,ll,rr,val);
    tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}

inline int query(int rt,int l,int r,int ll,int rr) {
    if(l>rr||r<ll) return 0;
    if(ll<=l&&r<=rr) return tr[rt];
    push_down(rt,l,r);
    int mid=(l+r)/2;
    int tmp=0;
    if(ll<=mid) tmp+=query(rt<<1,l,mid,ll,rr);
    if(rr>mid) tmp+=query(rt<<1|1,mid+1,r,ll,rr);
    return tmp;
}

inline bool check(int mid,int pos) {
    for ( int i=1;i<=n;i++ ) {
        if(mid>val[i]) op[i]=0;
            else op[i]=1;
    }
    build(1,1,n);
    for ( int i=1;i<=m;i++ ) {
        int opt=q[i].opt;
        int l=q[i].l;
        int r=q[i].r;
        if(!opt) {
            int gs=query(1,1,n,l,r);
            modify(1,1,n,l,r-gs,0);
            modify(1,1,n,r-gs+1,r,1);
        }
        if(opt) {
            int gs=query(1,1,n,l,r);
            modify(1,1,n,l,l+gs-1,1);
            modify(1,1,n,l+gs,r,0); 
        }
    }
    if(query(1,1,n,pos,pos)) return true;
    return false;
}

int main() {
    n=read();
    m=read();
    for ( int i=1;i<=n;i++ ) val[i]=read();
    for ( int i=1;i<=m;i++ ) {
        q[i].opt=read();
        q[i].l=read();
        q[i].r=read();
    }
    Q=read();
    int l=1,r=n;
    while(l<=r) {
        int mid=(l+r)/2;
        if(check(mid,Q)) {
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}