题目描述
有 n 个商贩,编号为 0 至 n−1。商贩 i 的商品价格为 ai。维护如下操作:
- 1 l r c:对每个 i∈[l,r],令 ai←ai+c。
- 2 l r d:对每个 i∈[l,r],令 ai←⌊ai/d⌋。商向下取整,包括负数。
- 3 l r:求 mini∈[l,r]ai。
- 4 l r:求 ∑i∈[l,r]ai。
输入格式
第一行两个整数 n,q,分别表示商贩数和操作数。
第二行 n 个整数 a0,…,an−1。
接下来 q 行,每行先给出操作编号,随后给出对应参数。
输出格式
对每个操作 3、4 各输出一行一个整数。
样例
10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9
-2
-2
-2
-2
0
1
1
数据范围
- 对于 30% 的数据,n,q≤103。
- 对于 60% 的数据,保证数据随机。
- 对于所有数据,1≤n,q≤105,0≤l≤r≤n−1,−104≤c≤104,2≤d≤109。
原 PDF 题面