3846. [雅礼集训 2017 Day1] 市场

【题目描述】

从前有一个贸易市场，在一位执政官到来之前都是非常繁荣的，自从他来了之后，发布了一系列奇怪的政令，导致贸易市场的衰落。

有 $n$ 个商贩，从 $0 \sim n - 1$ 编号，每个商贩的商品有一个价格 $a_i$ ，有两种政令；同时，有一个外乡的旅客想要了解贸易市场的信息，有两种询问方式：

   $1.$（政令） $l, r, c$ ，对于 $i \in [l, r], a_i \leftarrow a_i + c$

   $2.$（政令） $l, r, d$ ，对于 $i \in [l, r], a_i \leftarrow \lfloor {a_i}/{d} \rfloor$

   $3.$（询问）给定 $l, r$ ，求 $\min_{i \in [l, r]} a_i$

   $4.$（询问）给定 $l, r$ ，求 $\sum_{i\in [l, r]} a_i$

【输入格式】

第一行为两个空格隔开的整数 $n, q$ 分别表示商贩个数和政令 $+$ 询问个数。

第二行包含 $n$ 个由空格隔开的整数 $a_0 \sim a_{n - 1}$

接下来 $q$ 行，每行表示一个操作，第一个数表示操作编号 $1 \sim 4$ ，接下来的输入和问题描述一致。

【输出格式】

对于每个 $3、4$ 操作，输出询问答案。

【样例1输入】

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

【样例1输出】

-2
-2
-2
-2
0
1
1

【样例2】

点击下载样例2 

【数据规模与约定】

对于 $30\%$ 的数据， $n, q \leq 10 ^ 3$ ；

对于 $60\%$ 的数据，保证数据随机；

对于 $100\%$ 的数据， $1 \leq n, q \leq 10 ^ 5, 0 \leq l \leq r \leq n - 1, c \in [-10 ^ {4}, 10 ^ 4], d \in [2, 10 ^ 9]$

【来源】

LOJ