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