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）操作。
代码