問題一覧 > 通常問題

No.2170 Left Addition Machine

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : SPD_9X2SPD_9X2 / テスター : rin204rin204
2 ProblemId : 7092 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-30 23:08:32

問題文

Left Addition Machine は数列 $B$ を入力されると、以下の操作を $B$ の要素数が $1$ になるまで繰り返し、残った $1$ つの要素を出力します。

  • $B$ の中で最大値を取る項のうち、最も左にあるものを選択する。(ここでは、左から$i$ 項目であったとする。) $1 \le j < i$ を満たす全ての $j$ に関して、 $B_j := B_j + B_i$ をそれぞれ $1$ 回ずつ行う。($B$ の $j$ 項目に $B$ の $i$ 項目を加える。) その後、$B$ の $i$ 項目を削除する。


入力として、$N$ 項の数列 $A$ が与えられます。

加えて、 $Q$ 個のクエリが与えられます。 $i$ 番目のクエリは $L_i,R_i$ の $2$ 値で表されます。

各クエリに関して、 $A_{L_i},A_{L_i+1}, \cdots , A_{R_i} $ ( $A$ の $L_i$ から $R_i$ 項目までの連続部分列 )を Left Addition Machine に入力した場合に出力される値を $998244353$ で割った余りを答えてください。

なお、Left Addition Machineは $A$ に変更を加えることはありません。すなわち、各クエリは独立であり、前に処理したクエリによって後のクエリが影響を受けることはありません。

入力

$N\ Q$
$A_1\ A_2\ ...\ A_N$
$L_1\ R_1$
...
$L_Q\ R_Q$

  • 入力は全て整数
  • $1 \le N \le 2 \times 10^5$
  • $1 \le Q \le 2 \times 10^5$
  • $0 \le A_i < 998244353$
  • $1 \le L_i \le R_i \le N$

出力

$i$ 行目には、 $i$ 番目のクエリに対する回答を出力し、改行してください。

サンプル

サンプル1
入力
6 1
1 3 3 2 1 2
1 6
出力
3

以下に示すように数列は変化します。赤い数字は、最大の要素のうち、最左の要素です。
$ (1,\textcolor{red}{3},3,2,1,2) \rightarrow (\textcolor{red}{4},3,2,1,2) \rightarrow (\textcolor{red}{3},2,1,2) \rightarrow (\textcolor{red}{2},1,2) \rightarrow (1,\textcolor{red}{2}) \rightarrow (\textcolor{red}{3})$

サンプル2
入力
4 10
1 2 3 4
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4
出力
1
3
9
25
2
5
13
3
7
4

サンプル3
入力
11 10
5 7 9 9 0 5 6 2 3 5 998244352
1 10
4 9
3 4
1 3
2 6
4 10
5 6
5 7
7 10
1 11
出力
15
5
9
30
5
15
5
17
15
11

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。