【BZOJ 4534】基础排序练习题 / 题解

【BZOJ 4534】基础排序练习题 / 题解

原题地址
金策题解

题目描述

对于一个长度为 $n$ 的数组 $a[1], a[2], \cdots, a[n]$,定义这样一个算法:它包含 $m$ 个步骤,其中第 $i$ 步是将 $a[l_i], a[l_i+1], \cdots , a[r_i]$ 原地升序排序。

共有 $q$ 个询问,每个询问中给出一个初始数组 $a$,你要判断上述算法能否将这个数组升序排序(即最终是否满足 $a[i]\leq a[i+1], i = 1, 2, \cdots ,n-1$)。

输入格式

第一行三个整数 $n, m, q$,$n\leq 1500, m\leq 1 \times 10^6, q\leq 1500$。

接下来 $m$ 行按照顺序给出了算法中每个步骤的参数 $l_i, r_i$。

接下来 $q$ 行,每行表示一个询问,包含空格隔开的 $n$ 个非负整数 $a[1], a[2], \cdots, a[n]$。

输出格式

对于每个询问输出一行,如果上述算法能将这个数组升序排序,输出 $\text{AC}$,否则输出 $\text{WA}$。

样例输入

6 3 2
1 3
3 6
1 3
4 2 2 3 0 7
5 3 8 2 1 9

样例输出

AC
WA

思路

首先我们需要知道如何快速地对于一个区间进行排序

在上面这道例题中,我们利用二分将序列转化成了 01 序列,快速地对它进行了排序。对于一个操作区间 &[l_i, r_i]&,不管这里面原来的 0、1 顺序有多么杂乱,通过这一次排序就能把它变成前一部分为 0,后一部分为 1 的序列。那么我们逆向递推,就能找到能被给定的一系列操作排好序的初始序列。

但是这样的合法序列是指数级别的。我们能否找到一个快速的判定方法?

当然可以。我们假设一个形如 111000 的序列能被这些操作排好序,那么 100110 一定也行。对于确定的操作,初始序列中所有的 1 越靠近右边,这个序列就越有可能被这些操作成功排序。我们暂且称这个可能性为序列的“好”与“坏”。显然,$a$ 序列比 $b$ 序列好,当且仅当 $a$ 中第 $i$ 个 1 的位置比 $b$ 中第 $i$ 个 1 的位置靠后。也就是对于每一个位置,$a$ 的前缀 1 个数总是不大于 $b$ 的前缀 1 个数。

顺着这个思路,我们可以构造出对于给定操作区间的最坏初始序列:假设最后的升序序列是一个全排列,逆序将操作区间内的数字降序排序即可。得到这个最坏序列之后,我们就可以考虑如何回答每一个询问了。

现在我们得到了一个待排序的序列 $B$,第一件事情是将它离散化,然后将它转化成 01 序列,与我们一开始预处理的最坏序列 $C$ 进行比较。我们枚举 $k$,每一次两个 01 序列里,将数字 $k$ 出现的位置修改成为 1,判断每一个位置的前缀和即可。

具体实现,我们使用一棵线段树维护前缀和的最小值。每次在对应 $B$ 序列 $k$ 出现的位置 -1,在对应 $C$ 序列 $k$ 出现的位置 +1,如果前缀和最小值为非负,则 $B$ 序列一定比 $C$ 序列优秀。

时间复杂度 $\Theta((m+n^2+qn)\log n)$

代码

#include <bits/stdc++.h>
#define maxm 1001000
#define maxn 1505
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define min(a,b) (a<b?a:b)
struct ios{
    inline char read(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template <typename _Tp> inline ios & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
}io;
struct Node{
    int val,id;
    Node(int a=0,int b=0){
        val=a,id=b;
    }
    bool operator < (const Node &x) const{
        return val==x.val?id<x.id:val<x.val;
    }
}per[maxn];
struct Opera{
    int x,y;
    Opera(int a=0,int b=0){
        x=a,y=b;
    }
}ope[maxm];
int n,m,q,c[maxn],b[maxn];
int posc[maxn],posb[maxn];
std::set<int>s;
inline void Sort(int l,int r){
    int t=*s.upper_bound(l-1);
    while(t>=l&&t<r){
        s.erase(t);
        c[t]^=c[t+1]^=c[t]^=c[t+1];
        if (c[t-1]<c[t]) s.insert(t-1);
        if (c[t+1]<c[t+2]) s.insert(t+1);
        t=*s.upper_bound(l-1);
    }
}
int t[maxn<<2],a[maxn<<2];
inline void Pushup(int p){
    t[p]=min(t[ls],t[rs]);
}
inline void Pushdown(int p){
    int lp=a[p];a[p]=0;
    a[ls]+=lp;a[rs]+=lp;
    t[ls]+=lp;t[rs]+=lp;
}
inline void Update(int l,int r,int L,int R,int v,int p){
    if (l>=L&&r<=R){t[p]+=v;a[p]+=v;return;}
    if (a[p]) Pushdown(p);
    if (mid>=L) Update(l,mid,L,R,v,ls);
    if (mid<R) Update(mid+1,r,L,R,v,rs);
    Pushup(p);
}
int main(){
    io>>n>>m>>q;
    for (register int i=1;i<=n;++i) c[i]=i;
    for (register int i=1;i<n;++i) s.insert(i);
    for (register int i=1,l,r;i<=m;++i)
        io>>l>>r,ope[i]=Opera(l,r);
    for (register int i=m;i>=1;--i) Sort(ope[i].x,ope[i].y);
    for (register int i=1;i<=n;++i) posc[c[i]]=i;
    while(q--){
        memset(t,0,sizeof(t));
        memset(a,0,sizeof(a));
        for (register int i=1,x;i<=n;++i)
            io>>x,per[i]=Node(x,i);
        std::sort(per+1,per+1+n);
        for (register int i=1;i<=n;++i) b[per[i].id]=i;
        for (register int i=1;i<=n;++i) posb[b[i]]=i;
        bool flag=1;
        for (register int k=1;k<=n;++k){
            Update(1,n,posc[k],n,-1,1);
            Update(1,n,posb[k],n,1,1);
            if (t[1]<0){flag=0;break;}
        }
        puts(flag?"AC":"WA");
    }
}