前言：
從2006年的全國第一，到2012年的全國第二十；
從國家隊每年必有，到正式選手NOI Ag都拿不到；
時間可以改變一切，僅僅幾年，我們共同見證了一個省從強省變成弱??；
而無比奇(keng)特(die)的省選題，又使得許多難以想象的事情發生了；
不知現在，還有誰記得一年前的那場風波，兩年前的那場風波，三年前的那場風波；
不知現在，還有誰記得那些被奇(keng)特(die)的省選題和諧掉的眾神；
相關鏈接0相關鏈接1相關鏈接2———————————————————————————————————————————————————
今年，安徽省選終于不再是一場鬧劇。
希望這能成為一個轉折點。下面進入正題。
———————————————————————————————————————————————————
本沙茶還是考廢了……6題有3題被卡常數，而且卡到和暴力差不多的得分……
不過畢竟復仇成功了……好像還進了A隊……
不過像我這么弱到NOI也是被虐的份……
下面上題解：
【Day1】
coin：
首先那個貪心性質是比較好看出來的囧……就是如果每個面值都是上一個面值的正整數倍，則要得到一個價格的最小張數，總是先用最大的，不夠了再用第二大的……以此類推。
（證明：假設價格為s，某個方案(a1, a2...am)(ai為第i大的面值使用張數)對于最大的面值不是按照這樣的，則有s-a1*v1>=v1；若a2*v2>=v1，則將(v1/v2)張第二大的換成一張第一大的顯然更優，若a2*v2<v1，則可得s-a1*v1-a2*v2>=v1-a2*v2>=v2，可以對第三大的繼續分類討論，這樣一直到第m大的，必然會有一個出現可換成更大面值的情況，也就是該方案必然不是最優方案；如果最大的面值按照這樣，后面的面值不按照這樣，仍然如此）
這樣只要所有面值確定，配成任何一種價格的最優方案也就確定了，且可以隨著面值從大到小的一一確定，不斷更新最優方案；
由于本題價格<=100000，所以考慮搜索。一開始搜最大的面值，然后在搜后面的面值的時候，只能枚舉其因數。優化：
（1）初始定界：根據樣例2+簡單分析可以得出，使用2的冪的面值是一種比較優的方案，因此用它進行初始定界，可以大大方便后面的卡界；
（2）容易證明，如果所有價格中最大的為maxw，則最大的面值必然在[maxw/2, maxw]之間；
（3）很重要的剪枝：容易證明在最優方案中，相鄰兩個面值的比值必然是質數（否則設vi/v(i+1)不是質數，存在>1的因數d，則加入vi/d這個面值以后……）。因此，只需要預處理出2~100000間所有數的質因數即可；
（4）一些啟發式優化（卡界）；
（5）卡時；
綜合使用以上方法可以得到85~100分；注意搜索中的數組分層問題；
cube:
被卡常數了，真悲劇……
本題的猥瑣之處在于它的時空限制，時限1s，空限64M……給跪了！?。?br />只要求出(0, 0, 0)-(200, 200, 200)間的每個格子是否被覆蓋，然后再做一次floodfill就行了囧……
實現方法有很多，最好的是三維樹狀數組（改段求點，一個數組即可，且可以用short）。
問題是，本題的floodfill如何實現？遞歸DFS，爆棧；人工棧DFS，MLE；BFS，在壓位的情況下可以勉強卡過空間，但常數被卡了……
（求神犇好的解決辦法囧……）
square：
首先兩個不相交子矩形要么在X方向上不相交，要么在Y方向上不相交，要么在X、Y方向上都不相交……（廢話）
因此結果等于(X方向上不相交的全黑子矩形個數)+(Y方向上不相交的全黑子矩形個數)-(X、Y方向上都不相交的全黑子矩形個數)；
前兩個顯然灰常好求，第三個，只要求出每個點左上、右上、左下、右下四個方向里面的全黑子矩形個數，也灰常好求……
不過有一個細節：如何求出以某行/列為最下行/最右列的全黑子矩形個數？
一種方法是往左/右（或上/下）第一個比它矮的地方不斷迭代，但這樣遇到階梯狀的會被卡掉；
正確方法是找到往左/右（或上/下）第一個比它矮的地方，然后以這里為右下角的全黑子矩形個數=以那個地方為右下角的全黑子矩形個數+這里的高度*兩個位置的距離；
然后就是嚴格的O(N
2)了（不過數據很弱，本沙茶使用會被階梯狀的卡掉的辦法也AC了囧）；
至此Day1完掛。
【Day2】
（全DS題什么心態？？？？？？）
homework：
第一問……是人都會吧囧……
第二問……傻眼了囧……
其實看到第二問這種不能合并的東東就應該想到分塊……這里說一種時間復雜度為O(N
5/3)的分塊方法
注意本題的兩問都滿足區間減性質，即“A[l1..r1]中關于[l2..r2]范圍內的數的結果=A[l1..r1]中關于[0..r2]范圍內的數的結果- A[l1..r1]中關于[0..l2-1]范圍內的數的結果”。
因此，可以先對[l2..r2]這一維離線，然后按照值遞增的順序逐個加入A數組中的所有元素（一開始A數組為空），每加入一個數，就對l2或r2等于這個數的所有詢問計算結果，這樣原題就轉化為了這個問題：
一個長為N的序列，一開始所有位置都為空，現在有兩個操作：（1）在某個空位置插入一個數；（2）詢問目前某區間內的數的總數，以及不相同的數的總數；
這兩個問題都可以分塊解決：設S1[i][j]和S2[i][j]分別表示目前第i塊到第j塊中數的總數以及不相同的數的總數，同時維護bool FF[i][j][k]表示第i塊到第j塊是否出現數k。插入一個數時直接維護S1，根據FF維護S2即可。顯然塊大小sz應取N
2/3，總的時間、空間復雜度均為O(N
5/3)。
這樣……本題時限10s應該能過了吧囧……但是常數……萬惡的常數?。。。。。。ㄊ聦嵣虾?個點在本機上都是8.5s左右的，只有第4、5個點T，但在那里不知為什么幾乎全T了……）
disconnected：
這個……本沙茶真心不會搞囧……
@drcrow神犇說有一種按詢問分塊的辦法，其思想具體見他今年CTSC的論文……但本沙茶智硬理解不了……
求各位神犇解釋……
diff：
（很水的題，很坑爹的常數……本題真是推廣SAM的利器……）
本題的核心在于算任意兩個后綴的LCP之和，其它的很容易推導出來……
后綴的LCP，“正常人”的第一反應是SA……
求出SA及height后，轉化為線段樹問題……然后就直接搞定了……
但是……………………………………………………………………………………………………
本題N<=500000，時限2s！?。。。。。。。。。。。。。。。。。。。。。。。。。?！
如果求SA，不管是倍增還是DC3都會T（把SA求出來就T了）
因此，正解其實是SAM，把這個串的SAM求出來之后，直接用DFS求次序，再求height……這里的時間復雜度就是線性的了。
（WJMZBMR：現在SA早就過時了，要用SAM！?。〔?，其實SAM也過時了，現在是Suffix BST以及2
K Substring BST，但考慮到AH太弱了，同情一下，降低一點難度……）
至此AHOI Round2完掛。
（不過許多人都放水了囧……他們說我去年滾粗，太可憐了，要照顧我……于是我這樣的弱智就A隊了……）
（HSAAHNU進了6個……太可怕了，坐等NOI組團虐場……）