Mato is No.1

【1】IOI2009 hiring（這個在各大OJ上都找不到囧，只能看這里了囧，第11頁）
可以發現本題就是求一個比率rate，使得第i個人（如果用的話）工資為rate*Qi，并且還要滿足以下兩個限制條件：
（1）每人的最低工資限制：第i個人如果用的話，有rate*Qi>=Si，即rate>=Si/Qi；
（2）總開銷限制：rate*所有用的人的Q值之和<=W，即所有用的人的Q值之和<=W/rate。
這樣，可以先將所有人按照(S/Q)的值遞增排序，然后枚舉需要用的最后一個人（排序后的，也就是S/Q值最大的那個人），設為i，則總花費最省的做法顯然是取rate=Si/Qi。然后根據（2）式得出“所有用的人的Q值之和”的最大值W0=W/rate，其中，第i個人是必須要用的，故將W0值先減去Qi（若W0<Qi，則第i個人不可使用），剩下的問題就變成了在第0~(i-1)個人中（排序后的）選取一些人，使得他們的Q值之和不大于W0，并且選取的人盡可能多。顯然這可以用貪心來實現，即選取Q值最小的若干個人。接下來，由于題目中N<=500000，說明需要用數據結構來優化，可是Q的上限只有20000且Q為正整數，因此，線段樹是最好的選擇。建立一棵表示[1, 20000]的線段樹，每個結點存放兩個額外的值：sz和sum，分別表示Q值位于該結點代表的區間內的人的總數以及這些人的Q值總和。然后，需要解決上述子問題時，從根結點開始考察結點的sz值，不斷往下找即可（這有點像平衡樹的找第K小的操作）。
總時間復雜度：O(N * (log20000 + logN))（還有排序的時間）
代碼

【2】RQNOJ469
先按照任意一種屬性（這里為A）遞增排序，然后枚舉值i，排序后第1位~第i位的全部給A（看A屬性，它們中A屬性最大的一定是i），排序后第(i+1)位及以后的，看其B、C兩種屬性的大小，若B屬性更小就看B屬性，若C屬性更小就看C屬性，然后得出兩種屬性的最大值即可。因此可以得到下面的算法：先排序，然后將所有的毛的B或C屬性（哪種更小就看哪種）插入平衡樹（這里需要兩棵平衡樹，一棵存放B屬性的值，一棵存放C屬性的值），然后遞增枚舉i（注意i=0的情況不要漏掉），將第i位的B或C屬性在平衡樹中刪除，然后找出兩棵平衡樹中的最大值即可。
但是需要注意一種特殊情況：所有的毛都看同一個屬性，此時按照上面的算法可能求不出最優解，比如：
10 6 5
10 2 8
此時，第1個C屬性更小，第2個B屬性更小，若第1個看C屬性，第2個看B屬性，則總和為5+2=7，而如果兩個都看B屬性則總和為6。此時就需要特判（預先求出三種屬性中的最大值），然后再用上面的算法求解，就能保證求出最優解了。
代碼

【3】PKU2985
并查集+平衡樹基本操作，水題，不解釋。
代碼

【4】HNOI2011 括號匹配Brackets（目前可以看這個帖子）
Splay Tree維護序列問題。對于一段括號序列A[1..len]，定義優先級P[0..len]如下：
P[0]=0
P[i]=P[i-1]+1（i>0且A[i]為左括號）
P[i]=P[i-1]-1（i>0且A[i]為右括號）
然后，Splay Tree的每個結點需要記錄一個Z值和M值，分別表示該結點代表的括號序列中最后一個元素的優先級和優先級最小的元素的優先級。則可以證明：這段括號序列調整至平衡至少需要改變的括號數目為(-M+K+1) / 2，其中K=Z+((-M+1)/2)*2（注意這里的/是整除），此外由于有swap和invert兩個操作，因此需要記錄RM、TM、RTM值，分別表示將該括號序列執行swap操作后的序列的M值、執行invert操作后的序列的M值，以及同時執行swap和invert操作后序列的M值。
不過，本題需要嚴重注意的是：雖然replace操作的標記（代碼中的mk0）會覆蓋掉swap（代碼中的mk1）和invert（代碼中的mk2）操作的標記，但是在下放標記的時候，需要對三種標記逐一判斷，mk0和mk1、mk2并不是不能共存的！因為有可能先打上mk0標記后再打上mk1或mk2標記。
本題雖然是靜態的，但仍然不能使用線段樹，因為線段樹無法支持整體翻轉（rev）操作。
代碼