AT_waipc_qual_g.Sum of Max of Sum of K Segments

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ 和一个整数 $K$。定义函数 $f(L,R)$（$1 \leq L \leq R \leq N$）如下：

• 当 $R-L + 1 < K$ 时，令 $f(L,R)=0$。
• 否则，考虑从 $(A_L,A_{L+1},\ldots,A_R)$ 中取出 $K$ 个不相交的非空连续子序列。将“最左侧子序列的元素和的绝对值”与“其他子序列的元素和”相加，取所有可能方案中该值的最大值，作为 $f(L,R)$。更形式化地，$f(L,R)=\max_{L\leq l_1\leq r_1<l_2\leq r_2<\ldots<l_K\leq r_K\leq R}(|\sum_{l_1\leq i\leq r_1}A_i|+\sum_{2 \leq j \leq K}\sum_{l_j\leq i\leq r_j}A_i)$。

请计算 $\sum_{1 \leq L \leq R \leq N}f(L,R)$ 对 $998244353$ 取模后的值（如果为负数也要转化为 $0$ 到 $998244353-1$ 之间的数）。

输入通过标准输入给出，格式如下：

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

请输出答案。

样例解释 1

对于满足 $K \leq R-L+1$ 的 $(L,R)$，$f(L,R)$ 的值如下：

• 当 $(L,R)=(1,2)$ 时，$(l_1,r_1,l_2,r_2)=(1,1,2,2)$ 能取得最大值，因此 $f(L,R)=0$。
• 当 $(L,R)=(1,3)$ 时，$(l_1,r_1,l_2,r_2)=(1,1,3,3)$ 能取得最大值，因此 $f(L,R)=1$。
• 当 $(L,R)=(2,3)$ 时，$(l_1,r_1,l_2,r_2)=(2,2,3,3)$ 能取得最大值，因此 $f(L,R)=1$。

因此，这些 $f(L,R)$ 的总和为 $2$，即答案为 $2$。

数据范围

• $1 \leq K \leq N \leq 250000$
• $K \leq 4$
• $-10^9 \leq A_i \leq 10^9$
• 输入均为整数。

由 ChatGPT 5 翻译