No.3812 Max Min Sigma Problem
レベル :
/ AI推定難易度 : 1900
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 :
dyktr_06
/ テスター :
tyawanmusi
sepa38
タグ : / 解いたユーザー数 13
作問者 :
sepa38
問題文最終更新日: 2026-09-21 05:19:54
yukicoder contest 524
(順位表)
の他の問題:
問題文
長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
$1 \leq l \leq r \leq N$ を満たす整数 $l,r$ に対して、$f(l,r)$ を次のように定義します。
- $A_l,A_{l+1},\ldots,A_r$ の最大値を $X$、最小値を $Y$ とすると、$f(l,r)=(X-Y)^2$
$\displaystyle \sum_{l=1}^{N}\sum_{r=l}^{N}f(l,r)$ を $998244353$ で割ったあまりを求めてください。
制約
- $1 \leq N \leq 5 \times 10^5$
- $1 \leq A_i \leq 10^9$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
出力
答えを一行に出力してください。
サンプル
サンプル1
入力
3 1 2 3
出力
6
$\displaystyle \sum_{l=1}^{N}\sum_{r=l}^{N}f(l,r) = f(1, 1) + f(1, 2) + f(1, 3) + f(2, 2) + f(2, 3) + f(3, 3) = 0 + 1 + 4 + 0 + 1 + 0 = 6$ です。
サンプル2
入力
2 1 1000000000
出力
712559605
$998244353$ で割ったあまりを求めることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。