AHOI2013 Round2 Day2 简要题解

第一题：

　　第一问可以用划分树或主席树在O（nlog²n）内做出来。

　　第二问可以用树状数组套主席树在O（nlog²n）内做出来。

　　我的代码太挫了，空间刚刚卡过。。。（在bzoj上）

第二题：

　　分治，将询问分成两部分，每部分递归处理，每部分都把与询问无关的缩点。

　　还有个做法。。。here

第三题：

　　后缀数组+单调栈。后缀数组我写的是nlogn的，如果写的是O(n)的话，时间复杂度就是O(n)的了。（但是mato说求sa就会超时，弱菜不会后缀自动机，表示正在学习中(･_･;)）