P12498 「DLESS-1」Range | Sum | Maximum
题目描述
给出一个长度为 $n$ 的序列 $a$，定义一个区间 $[l,r]$ 的权值为 $\max_{l\le L\le R\le r}|\sum_{i=L}^Ra_i|$。
对于 $k=1,2,3,\dots,n$，求所有长度为 $k$ 的区间权值和。
输入格式
无
输出格式
无
说明/提示
#### 【样例解释】
样例中五组数据的 $ans$ 分别为：
- $\{4,3,2\}$
- $\{28,39,41,36,31,22,13\}$
- $\{28,39,41,36,31,22,13\}$
- $\{7,10,10,7\}$
- $\{18,23,19,14,7\}$
其中，对于第一组数据，各个区间的权值分别如下：
- $[1,1]:1$
- $[2,2]:1$
- $[3,3]:2$
- $[1,2]:1$
- $[2,3]:2$
- $[1,3]:2$
其中，长度为 $1$ 的区间有 $[1,1],[2,2],[3,3]$，权值和为 $4$；长度为 $2$ 的区间有 $[1,2],[2,3]$，权值和为 $3$；长度为 $3$ 的区间有 $[1,3]$，权值和为 $2$。
#### 【数据范围】
对于所有数据，保证：
- $1\le T\le10^4$
- $1\le n,\sum n\le10^6$
- $-10^6\le a_i\le10^6$
**本题采用打包测试**，各测试包描述如下：
| Subtask | $\sum n\le$ | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $500$ | 无 | $5$ |
| $2$ | $5000$ | 无 | $20$ |
| $3$ | $10^6$ | $a_i\ge 0$ | $25$ |
| $4$ | $3\times10^5$ | 无 | $25$ |
| $5$ | $10^6$ | 无 | $25$ |