版權屬于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 ;
}