Arithmetic Sequence Partitioning

In this problem, you are given a sequence of N integers \(v_1, v_2, \ldots, v_N\) where \(1 \leq N \leq 100{,}000\) and \(-100{,}000 \le v_i \le 100{,}000\). You need to process Q operations (\(1 \le Q \le 100{,}000\)). There are two types of operations:

• Update operation: A s t a b
  • Here \(s, t, a, b\) are integers with \(1 \le s \le t \le N\) and \(-100{,}000 \le a, b \le 100{,}000\).
  • This operation means that for every index \(i\) in the interval \([s, t]\) you add an arithmetic progression: specifically, update \(v_i\) to \(v_i + a + b \times (i-s)\).
• Query operation: B s t
  • Here \(s, t\) are integers with \(1 \le s \le t \le N\).
  • This operation asks: what is the minimum number of contiguous segments you can partition the subarray \([s, t]\) into so that every segment forms an arithmetic sequence?
  • For example, the sequence 1 2 3 5 7 can be partitioned into 2 segments: 1 2 3 and 5 7.

Your task is to help compute the standard answers for all these operations. For each query operation, output the required minimum number of segments.

Note on the arithmetic property: A sequence with one element is trivially an arithmetic sequence, and a sequence with two or more elements is arithmetic if the difference between consecutive elements is constant.

Hint: It may be effective to maintain an auxiliary array of consecutive differences \(D_i = v_{i+1} - v_i\) for \(1 \le i < N\) and use a lazy segment tree to support range updates and queries on the number of breakpoints (positions where the difference changes). When a query B s t is given (with \(s < t\)), the answer is \(1 +\) (number of indices \(i\) with \(s \le i \le t-2\) such that \(D_i \neq D_{i+1}\)).

inputFormat

The first line contains two integers \(N\) and \(Q\). The second line contains \(N\) integers \(v_1, v_2, \ldots, v_N\) representing the initial sequence. Each of the next \(Q\) lines describes an operation in one of the following two forms:

• A s t a b (update operation)
• B s t (query operation)

It is guaranteed that the operations satisfy the constraints described above.

outputFormat

For each query operation (lines beginning with B), output one line with a single integer representing the minimum number of segments into which the subarray \([s, t]\) can be partitioned so that every segment is an arithmetic sequence.

sample

5 5
1 2 3 5 7
B 1 5
A 2 4 1 1
B 1 5
B 3 5
A 1 3 -2 0
B 1 3

2
3
2
1