#P9039. [2017年备战省选]市场

[2017年备战省选]市场

题目描述

有 nn 个商贩,编号为 00 至 n−1n-1。商贩 ii 的商品价格为 aia_i。维护如下操作:

  • 1 l r c:对每个 i∈[l,r]i\in[l,r],令 ai←ai+ca_i\gets a_i+c。
  • 2 l r d:对每个 i∈[l,r]i\in[l,r],令 ai←⌊ai/d⌋a_i\gets\lfloor a_i/d\rfloor。商向下取整,包括负数。
  • 3 l r:求 min⁡i∈[l,r]ai\min_{i\in[l,r]}a_i。
  • 4 l r:求 ∑i∈[l,r]ai\sum_{i\in[l,r]}a_i。

输入格式

第一行两个整数 n,qn,q,分别表示商贩数和操作数。

第二行 nn 个整数 a0,…,an−1a_0,\ldots,a_{n-1}。

接下来 qq 行,每行先给出操作编号,随后给出对应参数。

输出格式

对每个操作 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%30\% 的数据,n,q≤103n,q\le10^3。
  • 对于 60%60\% 的数据,保证数据随机。
  • 对于所有数据,1≤n,q≤1051\le n,q\le10^5,0≤l≤r≤n−10\le l\le r\le n-1,−104≤c≤104-10^4\le c\le10^4,2≤d≤1092\le d\le10^9。

原 PDF 题面