第一题：
第一问可以用划分树或主席树在O（nlog2n）内做出来。
第二问可以用树状数组套主席树在O（nlog2n）内做出来。
我的代码太挫了，空间刚刚卡过。。。（在bzoj上）
第二题：
分治，将询问分成两部分，每部分递归处理，每部分都把与询问无关的缩点。
还有个做法。。。here
第三题：
后缀数组+单调栈。后缀数组我写的是nlogn的，如果写的是O(n)的话，时间复杂度就是O(n)的了。（但是mato说求sa就会超时，弱菜不会后缀自动机，表示正在学习中(?_?;)）
原文：http://www.cnblogs.com/hsuppr/p/3513832.html