數據結構選講

01-24

upd(DEC/17/2016):這裡是一份我外出講課的講稿，內容比較基礎，針對的是NOIP提高組選手。

接下來是一些難題：

Monotone Queue SPOJ.com - Problem HARBINGE

Heap - 2054 -- Color a Tree

Merge Heap - 3016 -- K-Monotonic

K-d Tree - JZPFAR(顧昱洲)

Chair Tree - SPOJ.com - Problem COT

Mo"s Algorithm - SPOJ.com - Problem COT2WC糖果公園

Merge of Segment Tree - SPOJ.com - Problem COT3

Suffix DataStructure - SPOJ.com - Problem COT4

Segment Tree "s Trick - SPOJ.com - Problem COT5

Block - SEAARCGERALD07

Divide and Conquer on Tree / balanced tree - Problem 2566. -- xmastree

Divide and Conquer on Tree / String - CTSC珠寶商

Dynamic SC - [Pa2011]Hard Choice

Bitset - Catch The Penguins 抓企鵝

Suffix DataStructure,KMP,Segment Tree SPOJ.com - Problem AE5A2

--------------------------------------------------------------------------------------------------------

upd（DEC／15／2016）：

我之前blog寫過一些數據結構的相關題目的整理和題解這邊也放出來吧。

# 樹形數據結構

### NOI2005 sequence

區間插入、刪除、統一修改、翻轉、求和、求最大子序列

`伸展樹`

### Spoj 10628. Count on a tree

無修改的區間/樹鏈上第K大

`劃分樹 or 主席樹`

### CTSC2008 nextwork

有修改的區間/樹鏈上第K大

`樹套樹`

### BZOJ3083: 遙遠的國度

樹的換根、鏈修改、子樹查詢

`樹鏈剖分`

### BZOJ2631 Tree(伍一鳴）

樹的合併、分離、加減、詢問

`Link-Cut Tree `

### Bzoj3132：上帝造題的七分鐘

子矩陣在線整體修改、求和

`前綴和的前綴和方法+二維線段樹上帝造題的七分鐘`

> 將標記分成四個修改(x,y)-(n,m)的標記

詢問(p,q)則為

然後就是一個維護二維前綴和的事了。

### bzoj2874: 訓練士兵

子矩陣先離線整體修改，再在線求和

`前綴和的前綴和方法+主席樹`

### bzoj1452: [JSOI2009]Count

支持兩種操作：改變子矩形中某個數，詢問某個子矩陣中某個數出現的次數。

`樹狀數組`

### Tsinsen A1302. JZPFAR(顧昱洲)

給出N個點，M個詢問點。詢問離某點距離第k大的點。

`K-d Tree`

### Tsinsen A1365. 森林旅店

給出N個點，Q個操作。操作為詢問離某點距離前k小的點或增加一個點。

`K-d Tree`

# 分塊思想

### 石家莊一中模擬賽p1裸

給一個長度為N的數列要求支持兩種操作

1.(l,r,x)將一段區間整體加一個整數x若元素小於0則該元素變為0

2.(l,r)詢問一段區間的和

`分塊後用堆維護`

### 廈門一中「炫動杯」NOIP2011 第四場模擬賽 p4

給一個長度為N的數列要求支持兩種操作

(l,r,x)將一段區間整體加一個整數

(l,r,C)詢問一段區間中有多少數不小於C

`分塊`

### Bzoj2821 作詩Poetize

求L-R出現偶數次數的數的個數

`分塊+二分`

### bzoj2741 【FOTILE模擬賽】L

在線詢問區間內的最大的連續XOR和

`分塊+Trie`

### 常州一中某夏令營模擬賽高速公路highway

一串長度為N的序列，要支持三個操作：

1、如果區間中沒有損壞的，就將區間所有數都減去一個值，答案加1，如果操作完後有元素小於等於0，則標記為損壞

2、將區間所有未損壞的元素都加上一個值

3、給p，將區間所有未損壞且小於p的元素都變成p

`分塊`

### Bzoj3005 體育課(sdoi2012)

一串長度為N的序列，要求支持三種操作：

1、給t，給L-R中的數分別加上(i-L+1)*t

2、交換兩個數

3、查詢L-R中的最大值

`分塊+單調隊列+二分`

> 分塊後問題實際轉化為對於其中的一塊支持三種操作：整體所有加一個t；給整體加一個增量t，即給第i個數加i*t；詢問最大值。這個問題是一個經典的斜率優化問題，可以用單調隊列預處理出每個元素的優勢區間（邊界考慮需細緻），詢問時二分查找當前增量即可。然後對於修改，整一塊打標記，剩下邊界暴力即可。詢問也分為整一塊詢問和剩下邊界暴力。交換直接對於兩個塊暴力修改即可。

複雜度O(N^1.5logN)

本題也可以做差可以轉換成最大前綴和。利用t非負也可以將複雜度優化為O(N^1.5)。

### bzoj2128: cheat

在線詢問某個子矩形中a到b之間的數的個數

`分塊`

### Bzoj2038: 小Z的襪子

詢問區間[L,R]中隨機抽出兩個顏色相同的概率。

`莫隊演算法`

### 10707. Count on a tree II

詢問樹鏈上不同顏色數。

`樹上莫隊演算法`

# 合併思想

### Codechef August Challenge 2013 :Sereja and Ballons

N個盒子，每個盒子Ai個球，事先給你M個區間(Li,Ri)，依次取出某個球，詢問當前有多少個區間其中的所有盒子為空.

`並查集+主席樹`

- 詢問即統計S(Ri)-S(Li-1)==0的數量，開始每個盒子都是獨立的塊，如果一個盒子i已空，就將i所在的塊與i-1所在的塊合併（因為值相同），新增的答案即為Li-1在i-1所在的塊且Ri在i所在的塊的詢問，發現是一個二維偏序的統計，利用主席樹預處理即可單次O(logN)詢問。

複雜度為O((N+Q)logN)/O(NlogN)。`

# 分治方法

### bzoj2738: 矩陣乘法（梁盾）

給你一個N*N的矩陣，每次詢問一個子矩形的第K小數。

`離線分治（整體二分）`

- 對於所有的詢問一起二分答案，那麼每次二分x後統計出所有詢問矩陣中不大於x的元素個數（二維樹狀數組即可），二分後詢問分為小於和不小於兩種，然後對兩種答案分別再二分即可（此時範圍減半）。注意做不小於的詢問時可以在原來樹狀數組的基礎上直接做，最後還原即可。

### Bzoj2683: 簡單題

離線矩陣單點修改，在線求和

`CQD分治`

### Bzoj2716: 天使玩偶

離線增加點，詢問離某點曼哈頓最近的點的距離。

`CQD分治`

# 樹的分治

### BZOJ2566 xmastree

給一顆點帶顏色的樹，支持修改點顏色和查詢最近相同顏色對。

`點的分治`

### Codechef August Challenge 2013 : Prime Distance On Tree

統計樹中dis(a,b)為質數的點對數量

`點的分治+FFT`

### BZOJ1267: Kth Number I

統計樹中dis(a,b)前K大的路徑。

`點的分治`