题目描述
对于一个长度为 $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");
}
}