P4635 [SHOI2011] Improved Code
Description
PP wrote two pieces of code to operate on an array.
For Pascal users, the two procedures are as follows:
```
procedure operate1(l, r, c : longint);
var
i : longint;
begin
for i := l to r do
a[i] := (a[i] + c) mod p;
end;
procedure operate2(l, r : longint);
var
i, cnt : longint;
begin
cnt := 0;
for i := l to r - 1 do
if a[i] > a[i + 1]
then cnt := cnt + 1;
writeln(cnt);
end;
```
For C / C++ users, the two functions are as follows:
```cpp
void operate1(int l, int r, int c)
{
int i;
for (i = l; i a[i + 1])
++ cnt;
printf("%d\n", cnt);
}
```
Then, the main program can operate on the array $a_i$ by calling these two subroutines. The following is sample code.
For Pascal users, the code is:
```
begin
operate1(1, 4, 3);
operate1(4, 7, 4);
operate2(1, 7);
end.
```
For C / C++ users, the code is:
```
int main()
{
operate1(1, 4, 3);
operate1(4, 7, 4);
operate2(1, 7);
}
```
However, QQ thinks PP’s program is too slow, and he wants you to optimize PP’s code. That is, given a main program that contains only two kinds of statements, `operate1` and `operate2`, and the initial values of the array $a_i$ before running, please compute the output of the program.
Input Format
The first line contains $3$ integers $n, m, p$. Here, $n$ is the upper bound of $l, r$ in the operations, $m$ is the number of statements in the main program, and $p$ is the value of the constant $p$ in the program.
In the next $n$ lines, each line contains one integer, which are the initial values of $a_1, a_2, \ldots, a_n$ in order. The input guarantees that these values are all within $0, 1, \ldots, p - 1$.
In the next $m$ lines, each line describes one line of code in the main program. Each line has one of the following two formats:
- `1 l r c`: represents the statement `operate1(l, r, c);`.
- `2 l r`: represents the statement `operate2(l, r);`.
Output Format
Output the output produced by the program corresponding to the given input.
Explanation/Hint
**Constraints and notes**
Test point $1$: $n \le 1000, m \le 2000$.
Test points $2 \sim 3$: $n \le 100000$, $m \le 200000$, $c \le 1$, $a_i \le 100000$, $p > 500000$.
Test point $4$: $n \le 100000, m \le 200000, l = 1, r = n$.
Test points $5 \sim 6$: $n \le 100000, m \le 200000$, and for all `operate1` parameters, $l = 1, r = n$.
Test points $7 \sim 10$: $n \le 100000, m \le 200000$.
It is guaranteed that $1 \le l \le r \le n$, $0 \le c \le 10^8$, $p \le 10^6$.
Translated by ChatGPT 5