P5743: 市场

传统题
4.000s 时间限制
256MB 内存限制
1 提交
0 解决
【题目描述】
从前有一个贸易市场，在一位执政官到来之前都是非常繁荣的，自从他来了之后，发布了一系列奇怪的政令，导致贸易市场的衰落。
有 n n n 个商贩，从 0∼n−1 0 \sim n - 1 0∼n−1 编号，每个商贩的商品有一个价格 ai a_i ai，有两种政令：
  1. l,r,c l, r, c l,r,c，对于 i∈[l,r],ai←ai+c i \in [l, r], a_i \leftarrow a_i + c i∈[l,r],ai←ai+c
  2. l,r,d l, r, d l,r,d，对于 i∈[l,r],ai←⌊ai/d⌋ i \in [l, r], a_i \leftarrow \lfloor {a_i}/{d} \rfloor i∈[l,r],ai←⌊ai/d⌋
现在有一个外乡的旅客想要了解贸易市场的信息，有两种询问方式：
  1. 给定 l,r l, r l,r，求 mini∈[l,r]ai \min_{i \in [l, r]} a_i mini∈[l,r]ai
  2. 给定 l,r l, r l,r，求 ∑i∈[l,r]ai \sum_{i\in [l, r]} a_i ∑i∈[l,r]ai
【输入】
第一行为两个空格隔开的整数 n,q n, q n,q 分别表示商贩个数和政令 + 询问个数。
第二行包含 n n n 个由空格隔开的整数 a0∼an−1 a_0 \sim a_{n - 1} a0∼an−1
接下来 q q q 行，每行表示一个操作，第一个数表示操作编号 1∼4 1 \sim 4 1∼4，接下来的输入和问题描述一致。
【输出】
对于每个 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\% 30% 的数据，n,q≤103 n, q \leq 10 ^ 3 n,q≤103；
对于 60% 60\% 60% 的数据，保证数据随机；
对于 100% 100\% 100% 的数据，1≤n,q≤105,0≤l≤r≤n−1,c∈[−104,104],d∈[2,109] 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] 1≤n,q≤105,0≤l≤r≤n−1,c∈[−104,104],d∈[2,109]

题目类型~

LibreOJ 

咻咻~

提交答案 状态