版权属于ZYXZYXZYX，想要引用此题（包括题面）的朋友请联系博主
题目来源：[2016国家集训队互测] 基础排序算法练习题（金策）
原题提交地址
分析：
防AK毒瘤题啊。。。
1. 预备技能——消逆序对排序：O(q(m+n²)log n)
对于一个序列，找到其中一个位置 i i 满足a[i]>a[i+1]a[i]>a[i+1]，交换 a[i] a [ i ] 和 a[i+1] a [ i + 1 ] ，重复这样的做法，直到不存在满足条件的 i i ，则序列被排好序。交换的次数等于逆序对的数量，而数量是n2n2级别的。
对于某一轮游戏，可以每次在待排序区间 [Li,Ri] [ L i , R i ] 内消逆序对。如果某个区间内的逆序对很少，那扫一遍区间是很浪费时间的。可以把满足条件的位置 i i 插入平衡树，对[Li,Ri][Li,Ri]这个区间进行消逆序对时只需要在平衡树中把 [Li,Ri) [ L i , R i ) 内的点依次取出，对序列修改后若产生新的满足条件的位置再插入即可。
其中平衡树可以使用 STL:set S T L : s e t ，只有 insert,erase,lowerbound i n s e r t , e r a s e , l o w e r b o u n d 三种操作。
在 m m 较大nn较小时， (m+n2)logn ( m + n 2 ) l o g n 的排序优于 mnlogn m n l o g n 的排序，但 q q 较大的时候依然会超时，只能通过3,4号点。
2. 转换——01序列
若要检验一个1−n1−n的排列能否被这 m m 次操作排好序，不需要对n!n!种排列进行检验，只需要对 2n 2 n 种 01 01 序列进行检验即可。这是排序网络的0-1原理，正确性很容易证明。
排序网络
3. 统计——逆向递推
下面研究具有什么性质的初始序列是可以被排序的。
先从01序列的特殊情况入手。一个最终被排好序的序列就是前面一段0，后面一段1，我们可以把 [Lm,Rm] [ L m , R m ] 这段中的数以任意方式打乱，得到的序列都是可通过第 m m 次操作排好序的序列。我们逆向递推，理论上就能得到每一次操作后能被以后的操作排好序的所有序列。
然而合法序列的个数是指数级的。
4. 精简——代表元素
若一个形如111000的序列能被正确排好序，那么101010必然也能被正确排好序。
我们需要一个对序列“好坏”程度的衡量标准，0越靠左，1越靠右，序列越接近升序，那么这个序列就越好。
因此容易发现，对区间[Li,Ri][Li,Ri]打乱顺序的最坏方式就是把1都放到左边，0都放到右边。对于一个序列 a a ，用pos(a,i)pos(a,i)表示 a a 中从左到右第ii个1所在的位置，若 a a 比bb优秀，当且仅当对于 i=1,2,…,k i = 1 , 2 , … , k 都有 pos(a,i)≥pos(b,i) p o s ( a , i ) ≥ p o s ( b , i ) 。
于是合法序列集的递推转化为了合法的最差元素的递推。
如果我们得到了能够被 m m 次操作排列有序的最差序列，那么任何一个比ta优秀的序列都可以通过这m此操作排列成有序的
5. 一步之遥——针对8号点的算法：O((m+n²)log n + qn)
8号点是01序列。先对序列使用消逆序对的方法排序（得到最差序列），然后对qq个询问每个 O(n) O ( n ) 检验。
6. 满分算法：O((m+n²+qn)log n)
不妨假设待排序的数组 A A 是一个nn排列。如果不是的话，可以将它先离散化，其中值相同的元素按照下标递增的顺序分配。容易看出这样并不会影响最终的答案。
现在尝试将01序列的算法推广到 n n 排列。对于初始排列A[1…n]A[1…n]和给定的 k k ，定义01序列BkBk，其中 Bk[i]=1 B k [ i ] = 1 当且仅当 A[i]≥k A [ i ] ≥ k 。
之前已经提到过，算法能将A数组正确排序，当且仅当对于所有 k=2,3,…,n k = 2 , 3 , … , n 该算法都能将01序列 Bk B k 正确排序。
根据刚才的算法，需要对每个 k k ，预处理出n−kn−k个0后跟 k k 个1的串倒着进行mm次操作后的结果 Ck C k 。
直接做肯定太慢了，我们可以做一件等价的事情：令初始排列为 1,2,…,n 1 , 2 , … , n ，按 i i 从mm到 1 1 的顺序，每次将[Li,Ri][Li,Ri]降序排序。（最差序列）
最后得到的序列中，将小于 k k 的值用0代替，其他用1代替，得到的01序列就是所求的CkCk，且 Ck C k 的某个位置的0改为1就可以得到 Ck−1 C k − 1 。
现在要对所有 k=2,3,…,n k = 2 , 3 , … , n 检查 Bk B k 是否比 Ck C k 优秀，即 Bk B k 的任何一个前缀的1都不能比 Ck C k 对应的前缀的1多。
如果我们把 Bk B k 中的1 取负号，在求完 k=i k = i 然后对 k=i−1 k = i − 1 求解时，就是加入一对新的 −1 − 1 和 +1 + 1 ，然后检查数组的每一个前缀和是否都非负，这个过程可以用线段树的区间加、维护区间最小值来实现（线段树维护前缀和序列）。
预处理过程依然用消逆序对的算法实现。
可通过100%的数据。
简单说一下我们的做法：
首先有一个递增序列 A A ，m个区间，我们把区间内的元素递减排列（这样就可以得到最差序列了），设为CC
（排序方法用 splay s p l a y 好了）
读入询问 B B 序列
枚举kk（ k k 的范围就是数值的范围啦）
每次把BB和 C C 中>=k>=k的元素设为1， <k < k <script type="math/tex" id="MathJax-Element-80"> （其中，因为我们是顺序枚举k，每次只会改变序列中的一个值）
把 B B 中的1取负号
比较BB和 C C 的前缀和之和，如果所有的前缀和之和都>=0>=0，则 B B 序列比CC优秀，可以完成排序
（改变序列只以及维护前缀和之和都可以用线段树完成）
tip
一开始被卡了一段时间，结果发现是pushdown的位置写错了？？？大雾
void change(int bh,int l,int r,int L,int R,int z) {
if (l>=L&&r<=R) {
minn[bh]+=z;
ad[bh]+=z;
return;
}
push(bh);
int mid=(l+r)>>;
if (L<=mid) change(bh<<,l,mid,L,R,z);
if (R>mid) change(bh<<|,mid+,r,L,R,z);
minn[bh]=min(minn[bh<<],minn[bh<<|]);
}
以我的习惯，都是push都是在最前面的
mmp，看来要改码风了。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
const int M=;
const int N=;
int n,m,q;
int c[N],posc[N],b[N],posb[N];
int minn[N<<],ad[N<<];
struct node{
int x,y;
};
node p[M];
set<int> s;
struct node2{
int val,id;
};
node2 f[N];
void Sort(int l,int r) { //将(l,r)降序排列
int i=*s.upper_bound(l-); //大于某值的迭代器
while (l<=i&&i<r) { //[l,r)
s.erase(i);
swap(c[i],c[i+]);
if (c[i+]<c[i+]&&c[i]>c[i+]) s.insert(i+);
if (c[i-]<c[i]&&c[i-]>c[i+]) s.insert(i-);
i=*s.upper_bound(l-);
}
}
void push(int bh) {
if (!ad[bh]) return;
int lc=bh<<;
int rc=bh<<|;
minn[lc]+=ad[bh]; ad[lc]+=ad[bh];
minn[rc]+=ad[bh]; ad[rc]+=ad[bh];
ad[bh]=;
}
void change(int bh,int l,int r,int L,int R,int z) {
//push(bh);
if (l>=L&&r<=R) {
minn[bh]+=z;
ad[bh]+=z;
return;
}
push(bh);
int mid=(l+r)>>;
if (L<=mid) change(bh<<,l,mid,L,R,z);
if (R>mid) change(bh<<|,mid+,r,L,R,z);
minn[bh]=min(minn[bh<<],minn[bh<<|]);
}
int cmp(const node2 &a,const node2 &b) {
return (a.val<b.val)||(a.val==b.val&&a.id<b.id);
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for (int i=;i<=m;i++) scanf("%d%d",&p[i].x,&p[i].y);
for (int i=;i<=n;i++) c[i]=i;
for (int i=;i<n;i++) s.insert(i); //降序排列,逆序对的起点
for (int i=m;i>=;i--) Sort(p[i].x,p[i].y);
for (int i=;i<=n;i++) posc[c[i]]=i; //c[i]的位置
while (q--) {
for (int i=;i<=n;i++) scanf("%d",&f[i].val),f[i].id=i;
sort(f+,f++n,cmp);
for (int i=;i<=n;i++) b[f[i].id]=i; //离散化
for (int i=;i<=n;i++) posb[b[i]]=i; //b[i]的位置
memset(minn,,sizeof(minn));
memset(ad,,sizeof(ad));
bool flag=;
for (int k=;k<=n;k++) {
change(,,n,posb[k-],n,); //b -1 k变大,k-1的位置变成了0
change(,,n,posc[k-],n,-); //c 1 k变大,k-1的位置变成了0
if (minn[]<) {flag=;break;}
}
if (flag) printf("AC\n");
else printf("WA\n");
}
return ;
}