P4243 [JSOI2009] Arithmetic Progression

"Given a sequence $a_i$ of length $l$, if the differences between adjacent numbers $a_i - a_{i-1}$ ($2 \leq i \leq l$) are all the same, then the sequence is an arithmetic progression." jyy, a top-level Martian math teacher, is teaching his Martian students.

To check how well the students have learned, jyy assigns an exercise: given a sequence of length $N$ ($1 \leq N \leq 100,000$), where initially the $i$-th number is $v_i$ ($v_i$ is an integer, $-100,000 \leq v_i \leq 100,000$), the students must modify some elements according to jyy’s operations. An operation has the form: `A s t a b` ($s, t, a, b$ are all integers, $1 \leq s \leq t \leq N$, $-100,000 \leq a, b \leq 100,000$). It means: over the interval $[s, t]$, add an arithmetic progression with initial term $a$ and common difference $b$. That is, $v_i$ becomes $v_i + a + b \times (i - s)$ (for $s \leq i \leq t$). Amid their hectic calculations, the poor Martian students must also answer jyy’s questions at any time. A query has the form: `B s t` ($s, t$ are integers, $1 \leq s \leq t \leq N$), which asks for the minimum number of segments into which the current interval $[s, t]$ can be partitioned so that each segment is an arithmetic progression. For example, `1 2 3 5 7` can be partitioned into $2$ segments: `1 2 3` and `5 7`. The answers to the queries must be computed and handed in as homework. Although the total number of operations plus queries is only $Q$ ($1 \leq Q \leq 100,000$), jyy still finds this problem boring and troublesome. So he wants you to compute a standard answer for him.

Line $1$: one integer $N$. Lines $2 \cdots N + 1$: each line contains one integer. Line $i + 1$ gives $v_i$. Line $N + 2$: one integer $Q$. Lines $N + 3 \cdots N + Q + 2$: each line describes an operation or a query, in the format described above, without quotes.

Several lines, each containing one integer, representing the answer to a query. Output the answers in the same order as the queries appear in the input.

Sample explanation: The original sequence is `1 3 -1 -4 7`. After the operation, the sequence becomes `1 2 3 5 7`. As described above, the minimum number of segments is $2$. Constraints: - For $30\%$ of the testdata, $N, Q \leq 5000$. - For $100\%$ of the testdata, $1 \leq N, Q \leq 100,000$. Translated by ChatGPT 5