【1】IOI2009 hiring（這個(gè)在各大OJ上都找不到囧，只能看
這里了囧，第11頁(yè)）
可以發(fā)現(xiàn)本題就是求一個(gè)比率rate，使得第i個(gè)人（如果用的話）工資為rate*Qi，并且還要滿足以下兩個(gè)限制條件：
（1）每人的最低工資限制：第i個(gè)人如果用的話，有rate*Qi>=Si，即rate>=Si/Qi；
（2）總開(kāi)銷限制：rate*所有用的人的Q值之和<=W，即所有用的人的Q值之和<=W/rate。
這樣，可以先將所有人按照(S/Q)的值遞增排序，然后枚舉需要用的最后一個(gè)人（排序后的，也就是S/Q值最大的那個(gè)人），設(shè)為i，則總花費(fèi)最省的做法顯然是取rate=Si/Qi。然后根據(jù)（2）式得出“所有用的人的Q值之和”的最大值W0=W/rate，其中，第i個(gè)人是必須要用的，故將W0值先減去Qi（若W0<Qi，則第i個(gè)人不可使用），剩下的問(wèn)題就變成了在第0~(i-1)個(gè)人中（排序后的）選取一些人，使得他們的Q值之和不大于W0，并且選取的人盡可能多。顯然這可以用貪心來(lái)實(shí)現(xiàn)，即選取Q值最小的若干個(gè)人。接下來(lái)，由于題目中N<=500000，說(shuō)明需要用數(shù)據(jù)結(jié)構(gòu)來(lái)優(yōu)化，可是Q的上限只有20000且Q為正整數(shù)，因此，線段樹(shù)是最好的選擇。建立一棵表示[1, 20000]的線段樹(shù)，每個(gè)結(jié)點(diǎn)存放兩個(gè)額外的值：sz和sum，分別表示Q值位于該結(jié)點(diǎn)代表的區(qū)間內(nèi)的人的總數(shù)以及這些人的Q值總和。然后，需要解決上述子問(wèn)題時(shí)，從根結(jié)點(diǎn)開(kāi)始考察結(jié)點(diǎn)的sz值，不斷往下找即可（這有點(diǎn)像平衡樹(shù)的找第K小的操作）。
總時(shí)間復(fù)雜度：O(N * (log20000 + logN))（還有排序的時(shí)間）
代碼【2】
RQNOJ469先按照任意一種屬性（這里為A）遞增排序，然后枚舉值i，排序后第1位~第i位的全部給A（看A屬性，它們中A屬性最大的一定是i），排序后第(i+1)位及以后的，看其B、C兩種屬性的大小，若B屬性更小就看B屬性，若C屬性更小就看C屬性，然后得出兩種屬性的最大值即可。因此可以得到下面的算法：先排序，然后將所有的毛的B或C屬性（哪種更小就看哪種）插入平衡樹(shù)（這里需要兩棵平衡樹(shù)，一棵存放B屬性的值，一棵存放C屬性的值），然后遞增枚舉i（注意i=0的情況不要漏掉），將第i位的B或C屬性在平衡樹(shù)中刪除，然后找出兩棵平衡樹(shù)中的最大值即可。
但是需要注意一種特殊情況：所有的毛都看同一個(gè)屬性，此時(shí)按照上面的算法可能求不出最優(yōu)解，比如：
10 6 5
10 2 8
此時(shí)，第1個(gè)C屬性更小，第2個(gè)B屬性更小，若第1個(gè)看C屬性，第2個(gè)看B屬性，則總和為5+2=7，而如果兩個(gè)都看B屬性則總和為6。此時(shí)就需要特判（預(yù)先求出三種屬性中的最大值），然后再用上面的算法求解，就能保證求出最優(yōu)解了。
代碼【3】
PKU2985并查集+平衡樹(shù)基本操作，水題，不解釋。
代碼【4】HNOI2011 括號(hào)匹配Brackets（目前可以看
這個(gè)帖子）
Splay Tree維護(hù)序列問(wèn)題。對(duì)于一段括號(hào)序列A[1..len]，定義優(yōu)先級(jí)P[0..len]如下：
P[0]=0
P[i]=P[i-1]+1（i>0且A[i]為左括號(hào)）
P[i]=P[i-1]-1（i>0且A[i]為右括號(hào)）
然后，Splay Tree的每個(gè)結(jié)點(diǎn)需要記錄一個(gè)Z值和M值，分別表示該結(jié)點(diǎn)代表的括號(hào)序列中最后一個(gè)元素的優(yōu)先級(jí)和優(yōu)先級(jí)最小的元素的優(yōu)先級(jí)。則可以證明：這段括號(hào)序列調(diào)整至平衡至少需要改變的括號(hào)數(shù)目為(-M+K+1) / 2，其中K=Z+((-M+1)/2)*2（注意這里的/是整除），此外由于有swap和invert兩個(gè)操作，因此需要記錄RM、TM、RTM值，分別表示將該括號(hào)序列執(zhí)行swap操作后的序列的M值、執(zhí)行invert操作后的序列的M值，以及同時(shí)執(zhí)行swap和invert操作后序列的M值。
不過(guò)，本題需要嚴(yán)重注意的是：雖然replace操作的標(biāo)記（代碼中的mk0）會(huì)覆蓋掉swap（代碼中的mk1）和invert（代碼中的mk2）操作的標(biāo)記，但是在下放標(biāo)記的時(shí)候，需要對(duì)三種標(biāo)記逐一判斷，mk0和mk1、mk2并不是不能共存的！因?yàn)橛锌赡芟却蛏蟤k0標(biāo)記后再打上mk1或mk2標(biāo)記。本題雖然是靜態(tài)的，但仍然不能使用線段樹(shù)，因?yàn)榫€段樹(shù)無(wú)法支持整體翻轉(zhuǎn)（rev）操作。
代碼