No.469 区間加算と一致検索の問題

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 31
作問者 : kimiyukikimiyuki / テスター : 紙ぺーぱー紙ぺーぱー

3 ProblemId : 1476 / 出題時の順位表

問題

長さ$N$の数列$x = (x_0, x_1, x_2, \dots, x_{N-1})$がある。 始めは数列$x = (0, 0, 0, \dots, 0)$とする。 以下の$2$種類のクエリが$Q$個与えられるので順番に処理せよ。

  • 区間加算クエリ ! L R K
    $L \le i \lt R$について、$x_i$を$x_i + K$に更新する。
  • 質問クエリ?
    数列$x$が現在と同一の値を最初にとるのは何番目のクエリの後であるか答える。 初期状態は$0$番目のクエリの後であるとする。
    つまり、答えようとしている質問クエリを$q$番目のクエリ($1 \le q \le Q$)とし、$i$番目のクエリの処理後の$x$の値を$x^i$と書く(初期状態のため$x^0 = (0, 0, 0, \dots, 0)$とする)としたとき、$\min \{ i \mid 0 \le i \le Q \land x^i = x^{q-1} \}$を出力する。

入力

N Q
$C_1$ ...
$C_2$ ...
...
$C_Q$ ...

$1$行目には、数列の長さを表わす整数$N$ ($1 \le N \le 10^6$)とクエリの数を表す整数$Q$ ($ 1 \le Q \le 10^5$)が与えられる。 $i+1$行目($1 \le i \le Q$)には、問題文中のクエリのいずれかの形式で与えられる。 ただし区間加算クエリであるとき、区間の左端$L_i$は$0 \le L_i \lt N$、区間の右端$R_i$は$L_i \lt R_i \le N$、加算する量$K_i$は $- 100 \lt K_i \le 100$を満たし、いずれも整数とする。

出力

質問クエリに対して、与えられた順番に答えを出力してください。 出力毎に改行してください。

サンプル

サンプル1
入力
3 6
! 1 3 1
! 0 2 2
! 0 3 -2
?
! 2 3 2
?
出力
3
1

処理は以下のように行われます。

  1. 始めは数列$x$は$x = (0, 0, 0)$である。
  2. $1$番目のクエリを処理する。その結果$x = (0, 1, 1)$になる。
  3. $2$番目のクエリを処理する。その結果$x = (2, 3, 1)$になる。
  4. $3$番目のクエリを処理する。その結果$x = (0, 1, -1)$になる。
  5. $4$番目のクエリに答える。この時点で$x$は$x = (0, 1, -1)$であり、$x$がこのような値をとるのは$3$番目のクエリを処理した後が最初であるので、$3$を出力する。
  6. $5$番目のクエリを処理する。その結果$x = (0, 1, 1)$になる。
  7. $6$番目のクエリに答える。この時点で$x$は$x = (0, 1, 1)$であり、$x$がこのような値をとるのは$1$番目のクエリを処理した直後と$5$番目のクエリを処理した後である。これらの中で最も早くに処理したクエリの番号である$1$を出力する。

サンプル2
入力
3 2
?
?
出力
0
0

サンプル3
入力
100000 6
! 0 100000 1
! 0 100000 2
! 0 100000 3
! 0 100000 4
! 0 100000 -7
?
出力
2

提出ページヘ