这规律真的是人类能找出来的吗？我考场上对着表画了 1 个小时左右才隐隐约约觉得这个序列是某两个序列拼起来的，还是没发现这就是 Fibonacci 数列套在序列上，考场上得有多强的直觉才能对着一列数找到这规律。Fibonacci 数进制也完全想不到 qwq

回复 @李星昊 : 抄题解没有任何意义

啊呀一个感叹号调试一下午

啊，没人做

竟然被卡在 memset 上，要注意 memset 是 $O(n)$，所以如果数组开太大，并且你要在循环里 memset 的话是很慢的，所以要注意数组开小点

回复 @Skylake
是初中有一次把咱叫去听高中的课的时候讲的，当时我听完大受震撼，以至于其他题都忘了就记着这一题hh

没看清楚提示，函数调用关系是DAG，不一定是一颗树

回复 @组撒头屯 :
不记得了欸，可能我还没听吧，这题正解反而简单一点，次解更巧妙

回复 @Skylake :
我记得好早之前的集训讲过这题，没记错应该是不停按二进制分两组跑最短路，不过具体分法也忘了

$\mathcal O(Tn\log n\log k)$ 的做法属实人类智慧，感觉比正解还巧妙

回复 @组撒头屯 :
线段树的话好像单次修改的时间复杂度就是 $O(n \log n)$，不太能过的样子
---------------------------------------------------------------------------
好吧，看来是方法不对

数据太弱？我错解（没后面的dp）拿90？

题面有误，出题人谢罪……
另外最后一个点大家注意特判长度为1的线段哦！

回复 @组撒头屯 :
az是我眼瞎了

回复 @Flyhouse :
《长度小于 r 且大于 l》
所有人赛时都这么写的，只有你的标算写的是“长度小于等于 r 且大于等于 l”，考虑赛时无法通知所有人只能改数据，不过现在你修一下题面也行

？？？为甚么改我的数据？？？
洛谷多个标程测试无误

回复 @组撒头屯 : 没看出来这可以直接分块 qwq，用珂朵莉树，每隔一段时间重构一次，时间复杂度不太行（算了下大概是 $\mathcal O(n\sqrt{m}\log{\sqrt{m}})$ 的样子），而且因为我懒，实现得常数很大，如果常数小点或许（？ 不开 O2 也能过
upd：看来是我查询的时候也把块拆开导致了不必要的重构，把查询改成暴力，重构时间拉长点就能过了

回复 @Skylake :
实际上线段树应该也是可行的，但是竟然没人写

@Skylake ，所以你写了个珂朵莉树?!

你最好有逝