問題一覧 > 通常問題

No.469 Range Addition and Matching Search Problem

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 43
作問者 : kimiyuki / テスター : 紙ぺーぱー
お気に入りにしたユーザー ProblemId : 1476 / 自分の提出
問題文最終更新日: 2026-10-20 14:54:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2016 (順位表) の他の問題:

Problem

There is a sequence $x = (x_0, x_1, x_2, \dots, x_{N-1})$ of length $N$. Initially, the sequence is $x = (0, 0, 0, \dots, 0)$. You are given $Q$ queries of the following $2$ types. Process them in order.

  • Range addition query ! L R K
    For $L \le i \lt R$, update $x_i$ to $x_i + K$.
  • Question query ?
    Answer after which query the sequence $x$ first took the same value as its current value. The initial state is regarded as the state after the $0$-th query.
    That is, let the question query being answered be the $q$-th query ($1 \le q \le Q$), and write $x^i$ for the value of $x$ after processing the $i$-th query (since it is the initial state, $x^0 = (0, 0, 0, \dots, 0)$). Then output $\min \{ i \mid 0 \le i \le Q \land x^i = x^{q-1} \}$.

Input

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

Line $1$ contains an integer $N$ ($1 \le N \le 10^6$) representing the length of the sequence and an integer $Q$ ($ 1 \le Q \le 10^5$) representing the number of queries. Line $i+1$ ($1 \le i \le Q$) contains a query in one of the formats described in the problem statement. For a range addition query, the left end $L_i$ of the range satisfies $0 \le L_i \lt N$, the right end $R_i$ of the range satisfies $L_i \lt R_i \le N$, and the amount to add $K_i$ satisfies $- 100 \le K_i \le 100$, all of which are integers.

Output

Output the answers to the question queries in the order they are given. Print a newline after each output.

Sample

Sample 1
Input
3 6
! 1 3 1
! 0 2 2
! 0 3 -2
?
! 2 3 2
?
Output
3
1

The processing proceeds as follows.

  1. Initially, the sequence $x$ is $x = (0, 0, 0)$.
  2. Process the $1$-st query. As a result, $x = (0, 1, 1)$.
  3. Process the $2$-nd query. As a result, $x = (2, 3, 1)$.
  4. Process the $3$-rd query. As a result, $x = (0, 1, -1)$.
  5. Answer the $4$-th query. At this point $x$ is $x = (0, 1, -1)$, and $x$ first takes this value after processing the $3$-rd query, so output $3$.
  6. Process the $5$-th query. As a result, $x = (0, 1, 1)$.
  7. Answer the $6$-th query. At this point $x$ is $x = (0, 1, 1)$, and $x$ takes this value right after processing the $1$-st query and after processing the $5$-th query. Output $1$, the number of the earliest processed query among these.

Sample 2
Input
3 2
?
?
Output
0
0

Sample 3
Input
100000 6
! 0 100000 1
! 0 100000 2
! 0 100000 3
! 0 100000 4
! 0 100000 -7
?
Output
2

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