回复 @Asm.Def :
orz夹心学长，同样的算法我写出来就TLE了-_-

回复 @TA :
我看BZOJ上的题面里有一句话：答案不超过1e9

可持久化线段树+启发式计算，理论复杂度是O(n*sqrt(n)*logn)的在线算法，但是免不了TLE的命运

看了大神们的Code竟然都是用的int。。我有点呵呵。

我擦我把暴力的long long改成int就A了。。这什么水数据。

暴力就T了一个。。。

今天晚上是怎么了……各种莫名奇妙的错误= =为何我直接递归dfs会运行错误啊卧槽……最后手工模拟了个递归栈=_=||||
第二次AC的这个版本我直接写成了括号序列，离线预处理部分（r1或r2的人数大于c的情况）利用括号序列上的线性扫描+计数（例如维护某一侧的左括号数-右括号数）可以做到O(N^2/c)，同理每次在线Query复杂度为O(|r1|+|r2|)，其实也就是O(c)。（可是我的递归dfs为什么会RE！如果是栈溢出的话为什么在本地连个segment fault都不给我= =？百思不得其解……）
唉…最后这几天专心复习期末考试吧……

居然是被题解误导了= =
求神犇们教我学分块……我这个三十多秒的是dfs序列上二分查找+树上的可持久化线段树+部分扫描……TAT而且我估计我最后算的时间复杂度是错的= =

回复 @Asm.Def :
233333

＂刷IOI的萌帝，比你们不知道高到哪里去了，我和他谈笑风生，你们呀，毕竟too young！＂

分块大法好……大力出奇迹……
代码正好100行啊蛤蛤蛤蛤蛤Θ••Θ
另外，虽然这里是离线的但人家这道题本来是强制在线所以用离线会掉节操的→_→