CSP-S 打炸了，然后晚上又打炸了，有点破防。

设 $$$f_{i,j}$$$ 表示 $$$k=i$$$，$$$a$$$ 序列中我已经选了前 $$$j$$$ 个。初始 $$$f_{1,0}=0$$$，其余为极大值。每次可以令 $$$k$$$ 加一，于是 $$$f_{i+1,j}=\min(f{i+1,j},f_{i,j})$$$。来考虑同层之间的转移，可以二分出极长合法段，设其长度为 $$$len$$$，只对 $$$f_{i,j+len}$$$ 转移显然是答案不劣的，但这样会导致方案统计少。考虑如下情况，$a$ 序列为 10 1 1，$b$ 序列为 11，我第一次不一定非要取出 $$$len=2$$$ 个才最优，显然也可以只取出 $$$1$$$ 个。因此，为了完成 D2，我们需要对 $$$[j+1,j+len]$$$ 都更新答案。我们可以使用 set 来维护这一过程。

具体地，set 维护当前所有合法转移及其方案数，每个 $$$f_{i,j}$$$ 的贡献在 $$$j+len+1$$$ 处消失，我们可以在那里删去它的贡献。注意到我们要合并 set 中的相同代价的转移的方案数，因此可以使用 mutable 关键字来完成。每次从 set 中取出最小值进行转移。注意，我们不能认为一个转移的方案数在模意义下为 $$$0$$$ 时等价于这个转移失效，应该额外记录，否则你过不了 pretest，应该 WA on 29。

下面这份代码中的注释是不用 set 维护而暴力转移的办法，可以配合理解。

Code

Ignoring TLE,let's calculate $$$f(s)$$$ at first.I'd like to transform the problem into this:divide the sequence into some segments whose length is more than 2,each segment's cost is the first number times the length -1.For example,2 2 2,it's cost is 4.Set $$$f_{i,j}$$$ means,explore first i elements,the first number of the last segment is j.It's easy to calculate now.

Means that,I can append $$$i_{th}$$$ number just in the back of the last segment,or make a new segment with $$$a_{i-1}$$$.

It costs $$$O(n)$$$ for each query,and got TLE.We can use ddp.Use matrix to draw the dp.Especially,the $$$\times$$$ means add.the $$$+$$$ means $$$\min$$$.Let $$$\min_i=\min_1^9 f_{i,j}$$$,we can design the vector as follows:

I'd like to show you $$$i_{th}$$$ matrix with $$$a_{i-1}=2$$$("i" means inf):

It's easy to use segment tree to solve this,but might TLE.Just use blocks,since the len of each query is const.

Also,I'm working on how to get the inverse of the matrix.Guass might work.

code