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

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

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

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

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

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

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

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

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

   于是組合數(shù)求出一個(gè)數(shù), 減去退化的情況.
   我們可以對(duì)共線的三點(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
   給一個(gè)長(zhǎng)度為n的序列,(n<100,000). 問(wèn)存在多少對(duì)l,r使得a1...l cons ar ...n-1的逆序數(shù)不超過(guò)k(k<long long)

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

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