CF 1061 E

? 还真没想到能这么做。

? 每天都可以买票，第 i 天票价为 \(a_i\) 元，每张票在激活后都可以用 k 天，k 为给定常数，每天可以买多张票，可以任选每张票的激活时间。

? 现在有 q 组询问，每组形如 l , r 表示只考虑第 l 天到第 r 天，要求每天都至少有一张票处于激活状态，求最小代价

? 不难发现，答案的形式应该为 \(a_l+\min(a_l,a_{l+1},...,a_{l+k-1})+...\) ，而且考虑到 k 是常数，那么可以将下标按 mod k 同余分类

? 现在假设一组内的下标为 \(h_1,h_2...h_m\) ，那么我想要求出 \(f_i\) = $\sum\limits_{k>=i}\min(h_i,...h_k) $

? 这个的转移可以考虑处理出来 \(\text{suf}_i\) 表示 i 后面第一个小于 \(h_i\) 的位置，那么就有转移 \(f(i)=(suf_i-i)\times h_i+f(suf_i)\)

? 现在有了 f 数组，那么考虑最终的答案应该如何用这个数组合并出来，用类似的思想，我们直接考虑 [l,r] 内和 l 在同一组的最小的 \(h_k\) ，设在同一组最大的下标为 j，求出这个可以用 ST 表。

? 那么最后答案即为 \(f_i-f_k+h_k\times (j-k+1)\)