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