「SHOI2011」改进代码
题目描述
PP 写了两段对数组进行操作的代码，分别为 operate1 和 operate2。
operate1(l, r, c)：对数组下标从 ( l ) 到 ( r ) 的元素执行 ( a[i] = (a[i] + c) \mod p )。operate2(l, r)：统计数组下标从 ( l ) 到 ( r-1 ) 中满足 ( a[i] > a[i+1] ) 的对数，并输出该计数。
现在需要优化这两段代码的执行，对于给定的初始数组和包含这两种操作的主程序，计算最终输出结果。
输入格式
第一行包含三个整数 ( n, m, p )，其中：
- ( n ) 是数组下标范围的上界，
- ( m ) 是主程序中的语句数，
- ( p ) 是取模常数。
接下来 ( n ) 行，每行一个整数，依次是 ( a_1, a_2, \dots, a_n ) 的初始值（均在 ( 0 \sim p-1 ) 范围内）。
再接下来 ( m ) 行，每行描述一条语句，格式为：
1 l r c：表示执行operate1(l, r, c)；2 l r：表示执行operate2(l, r)并输出结果。
输出格式
对于每个 operate2 操作，输出一行对应的计数结果。
样例
样例 1
输入：
7 3 7
2
5
3
0
3
1
2
1 1 4 3
1 4 7 4
2 1 7
输出：
2
样例 2
输入：
5 5 2
1
0
0
1
0
2 1 4
2 1 5
1 3 5 1
2 1 4
2 1 3
输出：
1
2
2
1
数据范围与提示
| 数据编号 | 数据限制 |
|---|---|
| 1 | ( n \leq 1000 )，( m \leq 2000 ) |
| 2~3 | ( n \leq 10^5 )，( m \leq 2 \times 10^5 )，( c \leq 1 )，( a_i \leq 10^5 )，( p > 5 \times 10^5 ) |
| 4 | ( n \leq 10^5 )，( m \leq 2 \times 10^5 )，( l=1 )，( r=n ) |
| 5~6 | ( n \leq 10^5 )，( m \leq 2 \times 10^5 )，所有 operate1 满足 ( l=1 )，( r=n ) |
| 7~10 | ( n \leq 10^5 )，( m \leq 2 \times 10^5 ) |
保证 ( 1 \leq l \leq r \leq n )，( 0 \leq c \leq 10^8 )，( p \leq 10^6 )。