题目描述
给定正整数 $p,b$,构造一张 $p$ 行无限列的数字表格,第 $i$ 行第 $j$列的数字为 $\frac{i}{p}$在$b$进制下的小数点后的第 $j$位。现在取出该表格的第 $k$列,设为 $a_1,...,a_p$,再给定 $b$个整数 $w_0,...,w_{b-1}$ 。接下来有 $q$ 次操作:
1 l r
:询问序列 $w_{a_l},..,w_{a_r}$的最大非空子段和;
2 x y
:把 $a_x$修改为$y$ 。
输入格式
第一行:四个整数 $p,b,k,q$。
第二行:$b$ 个整数,表示 $w_0,...,w_{b-1}$。
接下来 $q$行:每行表示一个操作
输出格式
对于每个询问,输出一行一个整数表示答案。
样例
13 10 3 8
1 10 -6 7 -9 -8 -5 8 3 4
1 2 5
2 7 3
2 7 6
1 1 7
2 6 1
1 1 13
2 2 5
1 2 10
16
17
17
10
17 13 10 10
1 10 -6 7 -9 -8 -5 8 3 4 -17 -16 12
2 17 7
2 10 11
1 4 13
2 14 12
1 1 17
2 16 0
1 5 13
1 6 7
2 14 10
1 10 12
12
34
12
8
-6
大样例
数据范围
$2\le p\le 10^9,2\le b\le 2\times 10^4,1\le k\le 10^9,1\le q\le 2\times 10^5$
子任务编号 | 分值 | 限制 |
---|---|---|
1 | $ 10$ | $p\le 2\times 10^5,k=1$ |
2 | $ 10$ | $p\le 2\times 10^5$ |
3 | $ 30$ | $k=1$ |
4 | $ 20$ | $q=1$ |
5 | $ 20$ | $没有2操作$ |
6 | $ 10$ | $无$ |