A
   一個有序數(shù)組A交換兩個數(shù)之后, 變成數(shù)組B, 現(xiàn)在給出數(shù)組B, 問它是否可能由一個A變化而來.

算法分析:
   
   送分題, 將B排序之后比較錯誤的位置, 我這個NC居然YY了一個奇葩方法然后WA掉了.
代碼: http://codeforces.com/contest/220/submission/2085314

B
   給一個長度為n(n<100,000)的序列, m(m<100,000)次詢問, 每次詢問區(qū)間[l,r]內(nèi)有多少個數(shù)X出現(xiàn)了X次.

算法分析:
   
   這樣的數(shù)不超過sqrt(n)個, 所以離線求出所有這樣的數(shù), 然后去更新所有的詢問.

代碼: http://codeforces.com/contest/220/submission/2076753
C
   有兩個n-排列(n<100,000){a},, 定義f(a,b) = min(abs(i,j)) when ai == bj. 求所有的循環(huán)與a的距離.

算法分析:
   
   維護(hù)兩個優(yōu)先級隊(duì)列A,B, A中存放的是所有(ai == bj && j >= i)的abs(i,j)值, B反之.
   所以A是不斷變大的, B是不斷變小的, 有兩種情況需要改變優(yōu)先級隊(duì)列的結(jié)構(gòu):
      B中元素減少到0 , 小case ~~
      循環(huán)的時候, 末尾的元素更新
   這樣涉及到元素的刪除, 我們肯定不能真的刪除, 而是選擇彈出"廢物"節(jié)點(diǎn).
   于是維護(hù)一個數(shù)組, 存放每個元素的當(dāng)前位置就可以了.

代碼: http://codeforces.com/contest/220/submission/2085278

D
   詢問在4000*4000的網(wǎng)格中, 面積是整數(shù)的三角形有多少個?

算法分析:
   不妨判斷面積乘以2等于偶數(shù)的三角形有的多少, 根據(jù)叉積推導(dǎo)面積, 發(fā)現(xiàn)至于三個頂點(diǎn)坐標(biāo)的奇偶性有關(guān).
   我們可以想像一個1*1的格子的四個點(diǎn)一定代表了四個種類的格子, 那么三個不同種類的格子肯定是不能構(gòu)成三角形了.
   然后暴力找規(guī)律發(fā)現(xiàn)有兩個奇偶性相同的格子一定能構(gòu)成面積是整數(shù)的三角形.

   于是組合數(shù)求出一個數(shù), 減去退化的情況.
   我們可以對共線的三點(diǎn)的最外兩點(diǎn)進(jìn)行統(tǒng)計(jì), 枚舉底和高, 4000*4000.
   然后乘以起點(diǎn)和中間點(diǎn), 中間點(diǎn)的數(shù)量就是底和高的gcd了.

代碼: http://codeforces.com/contest/220/submission/2100456

E
   給一個長度為n的序列,(n<100,000). 問存在多少對l,r使得a1...l cons ar ...n-1的逆序數(shù)不超過k(k<long long)

算法分析:
   維護(hù)l和r兩個值, 隨著l的增加, r單調(diào)不上升. 在這個過程中維護(hù)三個值:
      pl 1...l 的逆序數(shù)
      pr r...n-1的逆序數(shù)   
      pz 1...l中比r大的數(shù)
   隨著r的不斷增加我們可以用線段樹維護(hù)這三個值.

代碼: http://codeforces.com/contest/220/submission/2087403