3815. 基础排序算法练习题

【题目描述】

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

共有 $q$ 个询问，每个询问中给出一个初始数组 $a$，你需要判断上述算法能否将这个数组升序排序。

【输入格式】

第一行三个整数 $n,m,q$。

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

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

【输出格式】

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

【样例输入】

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

【样例输出】

AC
WA

【样例说明】

对于第一个测试点：$4\ 2\ 2\ 3\ 0\ 7\to \ [2\ 2\ 4]\ 3\ 0\ 7\to \ 2\ 2\ [0\ 3\ 4\ 7]\to \ [0\ 2\ 2]\ 3\ 4\ 7$，正确。 

对于第二个测试点：$5\ 3\ 8\ 2\ 1\ 9\to \ [3\ 5\ 8]\ 2\ 1\ 9\to \ 3\ 5\ [1\ 2\ 8\ 9]\to \ [1\ 3\ 5]\ 2\ 8\ 9$，错误。

【数据规模与约定】

对于所有数据，$1 \leq n \leq 1500,1 \leq m \leq 1000000,1 \leq q \leq 1500,1 \leq l_i,r_i \leq n,0 \leq a[i] \leq 1500$。

【来源】

《基础排序算法练习题》