Problem 1: Ai,Ai+1可以由Ai/2,Ai/2+1推出。递归即可。
Problem 2:我们将所有相邻的3角形间连一条边，容易看出答案是最长链长度+1。
Problem 3:
我们反过来计算所有内部为空的矩形个数。
我们一行行扫描，计算底边在当前行的空矩形个数。
令hc为第c列往上，在碰到障碍或底边之前，有几个空格子。
那么h1,h2,…,hm就决定当前的图。
拿个个图画一下，从最底下往上考虑，可以发现这构成了一个树形结构。
注意到将全体h+1很好实现，将一个h改成0，就意味着把树切成了两部分，由于随机数据，树高是logn的。。
复杂度就是nlogn。
Orz莫非是……神犇觉得NOI2011虐爆全场还不够，今年还要再虐一次……
哪里有题目啊
ORZ 给提前离场还虐爆全场的神跪了
回复cao_ximeng： www[dot]clarkok[dot]com/blog/?p=654在这里看到了题目大意……
Orz
膜拜！
Orz!
膜拜…ZJ省选果然是神题和神牛同时出没…
好意识流的题目和题解,给跪了
神犇虐一次还不够