問題一覧 > 通常問題

No.2931 Shibuya 109

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : kusirakusira / テスター : hirayuu_yc nouka28 👑 loop0919 tnodino amesyu Nyaa Uruzu
4 ProblemId : 11323 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-12 14:04:56

問題文

1, 0, 9 のいずれかからなる長さ NN の数列 AA があります。
1≤l≤r≤N1 \le l \le r \le Nなる整数組 (l,r)(l, r) に対し、関数 f(l,r)f(l ,r) を次のように定義します。

f(l,r):=f(l, r) := 数列 AA の ll 番目から rr 番目までを文字列とみなして結合し、それを1010 進数の数とみなしたときの値
⌊f(l,r)9⌋\left\lfloor\frac{f(l, r)}{9}\right\rfloor の桁和を答えてください。

QQ 個のクエリに答えてください。

桁和とは 正整数 nn の桁和を 1010 進法で表したときの各桁の和として定義します。例えば 20242024 の桁和は 2+0+2+4=82+0+2+4=8 です。

制約

  • 1≤N,Q≤5×1051 \le N, Q \le 5 \times 10^5
  • Ai∈A_i \in {0,1,90, 1, 9}
  • 1≤l≤r≤N1 \le l \le r \le N
  • Al≠0A_l \neq 0
  • Ai=1 (1≤i≤N)A_i = 1 \ (1 \le i \le N)を満たす ii は高々 88 個
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えらる。

N QN\ Q
A1 A2 ⋯ ANA_1\ A_2\ \cdots\ A_N
l1 r1l_1\ r_1
l2 r2l_2\ r_2
⋮\vdots
lQrQl_Q r_Q

出力

QQ 行出力せよ。ii 個目のクエリの答えを ii 行目 (1≦i≦Q)(1 \leqq i \leqq Q)に出力せよ。

サンプル

サンプル1
入力
9 3
1 0 9 1 0 9 1 0 9
3 5
1 4
1 9
出力
2
4
18

1つめのケースについて、数列 AA の 33 番目から 55 番目を文字列として結合した値は 910910 であり、f(3,5)f(3, 5) は 910910 です。
⌊f(3,5)9⌋=⌊9109⌋=101\left\lfloor\frac{f(3, 5)}{9}\right\rfloor = \left\lfloor\frac{910}{9}\right\rfloor = 101 であるため、桁和は 2(=1+0+1)2(=1+0+1)です。

サンプル2
入力
23 8
1 0 1 9 1 0 1 0 0 0 9 1 9 9 0 9 1 0 0 0 0 1 1
4 20
5 22
1 19
11 22
3 14
13 20
3 3
22 23
出力
44
51
74
19
33
6
0
1

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