原题地址
金策题解

题目描述

对于一个长度为 $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}$。

样例输入

样例输出

思路

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

在上面这道例题中,我们利用二分将序列转化成了 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)$

代码