title

BZOJ 4552

LUOGU 2824

题意：

给出一个 \(1\sim n\) 的全排列，现在对这个全排列序列进行 \(m\) 次局部排序，排序分为两种：

1. 0,l,r 表示将区间 \([l,r]\) 的数字升序排序；

2. 1,l,r 表示将区间 \([l,r]\) 的数字降序排序；

最后询问第 \(q\) 位置上的数字。

analysis

题意简单明了，这个序列如果转化成 \(01\) 序列，那么应该比原来的序列好做很多了。

因为可以用 \(O(\log n)\) 的算法实现 \(01\) 序列排序，我们使用线段树来维护。

查询一段区间内的 \(1\) 的个数记为 \(num\) ，如果是升序，就将这段区间的 \([r-num+1, r]\) 都更改为 \(1\) ，将 \([l, r-num]\) 更改为 \(0\) 。降序则将 \([l, l+num-1]\) 更改为 \(1\) ，将 \([l+num, r]\) 更改为 \(0\) 。（注意：当 \(num=0\) 时，直接将 \([l,r]\) 更改为 \(0\) ，避免出现 \(L>R\) 而造成 \(RE\) ）。

这样我们就成功地把排序转化为了区间查询和区间修改。

然后对于这道题呢，扫一遍肯定就挂了，那就要二分答案了。

当然，这样的话，只能离线做了。

二分答案 \(mid\) ，把原序列中 \(\geqslant m\) 的都更改为 \(1\) ，把原序列中 \(<m\) 的都更改为 \(0\) ，对于每次操作，把 \(01\) 序列排序（就是上面所说的线段树 \(01\) 排序），如果 \(q\) 的位置上还是 \(1\) 的话，那么就是可行的答案。

而且二分一个值成立 当且仅当 这个位置的值 \(\geqslant m\) ，所以如果 \(check\) 返回 \(true\) ，则 \(l=mid+1\)，否则 \(r=mid-1\) 。

code

#include<bits/stdc++.h>

const int maxn=1e5+10;

namespace IO
{
    char buf[1<<15],*fs,*ft;
    inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
    template<typename T>inline void read(T &x)
    {
        x=0;
        T f=1, ch=getchar();
        while (!isdigit(ch) && ch^'-') ch=getchar();
        if (ch=='-') f=-1, ch=getchar();
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
        x*=f;
    }

    char Out[1<<24],*fe=Out;
    inline void flush() { fwrite(Out,1,fe-Out,stdout); fe=Out; }
    template<typename T>inline void write(T x,char str)
    {
        if (!x) *fe++=48;
        if (x<0) *fe++='-', x=-x;
        T num=0, ch[20];
        while (x) ch[++num]=x%10+48, x/=10;
        while (num) *fe++=ch[num--];
        *fe++=str;
    }
}

using IO::read;
using IO::write;

int a[maxn];
namespace SGT
{
    int tree[maxn<<2],atag[maxn<<2];
    inline void build(int x,int l,int r,int k)
    {
        if (l==r)
        {
            tree[x]=a[l]>=k;
            atag[x]=0;
            return ;
        }
        int mid=(l+r)>>1;
        build(x<<1,l,mid,k);
        build(x<<1|1,mid+1,r,k);
        tree[x]=tree[x<<1]+tree[x<<1|1];
        atag[x]=0;
    }

    inline void pushdown(int x,int l,int r)
    {
        int mid=(l+r)>>1;
        if (atag[x]==1) tree[x<<1]=mid-l+1, tree[x<<1|1]=r-mid;
        else tree[x<<1]=tree[x<<1|1]=0;
        atag[x<<1]=atag[x<<1|1]=atag[x];
        atag[x]=0;
    }

    inline void Change(int x,int l,int r,int tl,int tr,int k)
    {
        if (tl>r || l>tr) return ;
        if (tl<=l && r<=tr)
        {
            tree[x]=k*(r-l+1);
            atag[x]=k ? 1 : -1;
            return ;
        }
        if (atag[x]) pushdown(x,l,r);
        int mid=(l+r)>>1;
        Change(x<<1,l,mid,tl,tr,k);
        Change(x<<1|1,mid+1,r,tl,tr,k);
        tree[x]=tree[x<<1]+tree[x<<1|1];
    }

    inline int query(int x,int l,int r,int tl,int tr)
    {
        if (tl>r || l>tr) return 0;
        if (tl<=l && r<=tr) return tree[x];
        if (atag[x]) pushdown(x,l,r);
        int mid=(l+r)>>1;
        return query(x<<1,l,mid,tl,tr)+query(x<<1|1,mid+1,r,tl,tr);
    }

    inline int queryPoint(int x,int l,int r,int k)
    {
        if (l==k && k==r) return tree[x];
        if (atag[x]) pushdown(x,l,r);
        int mid=(l+r)>>1;
        if (k<=mid) return queryPoint(x<<1,l,mid,k);
        else return queryPoint(x<<1|1,mid+1,r,k);
    }
}

using SGT::build;
using SGT::query;
using SGT::Change;
using SGT::queryPoint;

int n,m,q;
int opt[maxn],L[maxn],R[maxn];
inline bool check(int x)
{
    build(1,1,n,x);
    for (int i=1; i<=m; ++i)
    {
        int num=query(1,1,n,L[i],R[i]);
        if (!num) { Change(1,1,n,L[i],R[i],0); continue; }//避免出现 L>R 的情况
        if (!opt[i]) Change(1,1,n,R[i]-num+1,R[i],1), Change(1,1,n,L[i],R[i]-num,0);
        else Change(1,1,n,L[i],L[i]+num-1,1), Change(1,1,n,L[i]+num,R[i],0);
    }
    return queryPoint(1,1,n,q);
}

int main()
{
    read(n);read(m);
    for (int i=1; i<=n; ++i) read(a[i]);
    for (int i=1; i<=m; ++i) read(opt[i]),read(L[i]),read(R[i]);
    read(q);
    int l=1, r=n, ans=0;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (check(mid)) ans=mid, l=mid+1;
        else r=mid-1;
    }
    write(ans,'\n');
    IO::flush();
    return 0;
}

BZOJ 4552: [Tjoi2016&Heoi2016]排序 二分答案 线段树01排序

原文：https://www.cnblogs.com/G-hsm/p/11482149.html