#P1319. Extreme Extension
Extreme Extension
题意翻译
对于一个数列,定义一次操作为选择数列中任何一个元素 ,将这个位置替换成两个正整数 满足
定义一个数列的极端值为将这个数列变成不降数列的最小操作次数
给定一个长度为 的数列 ( ),让你求它的所有非空子段的极端值之和,对 取模
一个测试点中有多组数据,保证所有数据 的规模总和不超过
4
3
5 4 3
4
3 2 1 4
1
69
8
7264 40515 28226 92776 35285 21709 75124 48163
5
9
0
117
提示
对于 的数据,满足 , , 。
对于 的数据,满足 , , 。
对于 的数据, 满足 , 且 , 。
定义 为序列 的极值。
在第一个测试案例中,
- ,因为 YouKn0wWho 可以对子序列 进行以下操作(新插入的元素已被下划线标记):$ [5, 4, 3] \rightarrow [\underline{3}, \underline{2}, 4, 3] \rightarrow [3, 2, \underline{2}, \underline{2}, 3] \rightarrow [\underline{1}, \underline{2}, 2, 2, 2, 3] $;
- ,因为 $ [5, 4] \rightarrow [\underline{2}, \underline{3}, 4] $;
- ,因为 $ [4, 3] \rightarrow [\underline{1}, \underline{3}, 3] $;
- ,因为它们已经是非递减的。
因此,所有子序列的极值的总和为 的值为 。