No.469 Range Addition and Matching Search Problem
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.
- Initially, the sequence $x$ is $x = (0, 0, 0)$.
- Process the $1$-st query. As a result, $x = (0, 1, 1)$.
- Process the $2$-nd query. As a result, $x = (2, 3, 1)$.
- Process the $3$-rd query. As a result, $x = (0, 1, -1)$.
- 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$.
- Process the $5$-th query. As a result, $x = (0, 1, 1)$.
- 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もしくは右上の雲マークをクリックしてアカウントを作成してください。
紙ぺーぱー