Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:1024 MB
Statistics

题目描述

给定正整数 $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$ $无$