l253. A - 區間最小值總和問題 - 高中生程式解題系統

內容

給你一個長度為 $N$ 的正整數數列 $(A_{1}, A_{2}, A_{3}, . . ., A_{N})$ ，定義 $MIN(S)$ 代表一個集合 $S$ 裡面最小的那個值，例如 : $MIN (1, 3, 4) = 1$ ，想請你求所有數對 $(l, r)$ 符合 $1 \leq l \leq r \leq N$ 的 $MIN (A_{l}, A_{l + 1}, . . ., A_{r})$ 的總和，也就是請你求以下的東西 :

$\sum_{l = 1}^{N} \sum_{r = l}^{N} MIN (A_{l}, A_{l + 1}, . . ., A_{r})$

因為答案有點大，請模 $998244353$ 。

輸入說明

輸入第一行有個正整數 $N$ ，代表序列的長度。

接著一行有 $N$ 個正整數，兩個數中間以空格隔開，第 $i$ 個數代表 $A_{i}$ 。

$1 \leq N \leq 10^{6}$
$1 \leq A_{i} \leq 998244352$

輸出說明

輸出 $\sum_{l = 1}^{N} \sum_{r = l}^{N} MIN (A_{l}, A_{l + 1}, . . ., A_{r}) mod 998244353$

範例輸入 #1

3
1 3 2

範例輸出 #1

範例輸入 #2

10
3 1 4 1 5 9 2 6 5 3

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (10%): 1.0s , <1K
不公開測資點#1 (10%): 1.0s , <1K
不公開測資點#2 (10%): 1.0s , <1K
不公開測資點#3 (10%): 1.0s , <1M
不公開測資點#4 (10%): 1.0s , <1M
不公開測資點#5 (10%): 1.0s , <10M
不公開測資點#6 (10%): 1.0s , <10M
不公開測資點#7 (10%): 1.0s , <10M
不公開測資點#8 (10%): 1.0s , <10M
不公開測資點#9 (10%): 1.0s , <10M

提示：

範例輸入 # 1

根據輸入， $A = (1, 3, 2)$ 。

$(l, r) = (1, 1)$ 時， $MIN (1) = 1$ 。

$(l, r) = (1, 2)$ 時， $MIN (1, 3) = 1$ 。

$(l, r) = (1, 3)$ 時， $MIN (1, 3, 2) = 1$ 。

$(l, r) = (2, 2)$ 時， $MIN (3) = 3$ 。

$(l, r) = (2, 3)$ 時， $MIN (3, 2) = 2$ 。

$(l, r) = (3, 3)$ 時， $MIN (2) = 2$ 。

所求為 $1 + 1 + 1 + 3 + 2 + 2 = 10$ 。

範例輸入 # 2

總共有 $55$ 組相異的 $(l, r)$ ，答案加起來為 $107$ 。

Authored by r1cky

標籤:

出處:

第一屆Chi怪壓常比賽 [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
36776	r1cky (hehe)	l253		329	2023-08-08 10:10