感谢 @3725

可能爆搜比带空串转移的DFA匹配快一点……

数据没传对，已修复

回复 @@@@ :
您真是个天才。1A.

记的用 multiset ，不能用set，实测WA3个点。

强行map

想到了严格 $O(n\log(n))$ 的解法:
首先我们用单调栈或者 $\text{std::set}$ 预处理出每个值 $a_l$ 右边第一个不大于它的值 $a_r$ 的位置, 这样的话区间 $(l,r)$ 就是以 $l$ 为左端点的合法区间的右端点的可能位置.
然后我们根据 $r$ 的大小升序排序, 同时使用一个树状数组维护 $a_i$ 后大于前面所有点的点值 $a_r$ 与位置 $r$ (若点值相等取下标更小的), 将点逐个加入树状数组, 在加入到某个 $(l,r)$ 的 $r-1$ 的位置的时候就可以查询 $l$ 得到最大的右端点.
总时间复杂度中, 预处理是 $O(n)$ 或者 $O(n\log(n))$ 的, 最后树状数组中每个点都至少要插入/查询一次, 树状数组部分总时间复杂度 $O(n\log(n))$, 整个程序时间复杂度为 $O(n\log(n))$.
最后注意特判 $ans=0$ 的情况就行了
可以参考标程理解一下

线段树分治
Q可能等于0

莫队要开O2才能过，我太蒟蒻了

BZOJ AC，COGS50分。。求神犇指错。。。（代码略丑

就是求一下树的直径么

INF设小了会T

回复 @Hzoi_QTY :
指针不是消耗空间更大吗？

友情提示：数组的话内存只需要开$O(N+MlogN)$即可。
（有人能告诉我你们为啥都用指针吗？）
计算器是个好东西（划掉

忽然发现自己很久以前的代码有点毛病……为了水BZOJ3306调了半下午

数据太弱了，建议管理员加强数据，刚才写了个错误的代码结果AC了……

爆栈啦~\(≧▽≦)/~

呃...memset GG了...虽然之前犯过这样的错误但还是错了....

评测鸡应该是被阉割过的......39997这组数据本机不开O2只要0.4s放评测鸡上就T掉了......
而且就算是99999在本机开O2也只要0.6s，很普通的学校机
不就是两个log的分治NTT吗，复砸度是对的啊......
DAG I也有点卡常 (╯°Д°)╯︵┴┴