P14293 [JOI2024 预选赛 R2] 购物 2 / Shopping 2

JOI 商店有 $N$ 件商品，每件商品被编号为从 $1$ 到 $N$。 每件商品都有一个**定价**和**种类**。商品 $i$（$1 \le i \le N$）的定价为 $P_i$ 日元。商品的种类用 $1$ 到 $M$ 之间的整数表示，商品 $i$（$1 \le i \le N$）的种类为 $A_i$。 JOI 商店决定举行一次促销活动。促销持续 $M$ 天，在第 $j$ 天（$1 \le j \le M$），所有种类为 $j$ 的商品均以定价的一半价格出售。 在促销期间，共有 $Q$ 位顾客访问了 JOI 商店。每位顾客被编号为从 $1$ 到 $Q$。顾客 $k$（$1 \le k \le Q$）在促销的第 $T_k$ 天访问商店，并购买了商品 $L_k, L_k+1, \cdots, R_k$ 各一件。 为了评估促销的效果，商店希望知道每位顾客购买商品所花费的金额。 给定商品信息和顾客信息，编写一个程序，计算每位顾客购买商品所花费的金额。

输入以如下格式给出： $N\ M\ Q$ $P_1\ A_1$ $P_2\ A_2$ $\vdots$ $P_N\ A_N$ $T_1\ L_1\ R_1$ $T_2\ L_2\ R_2$ $\vdots$ $T_Q\ L_Q\ R_Q$

输出 $Q$ 行。第 $k$ 行（$1 \le k \le Q$）应输出顾客 $k$ 购买商品所花费的金额，单位“日元”省略不写。

### 样例 1 解释 顾客 1 购买商品所花费的金额为 $40 \div 2 + 30 \div 2 + 20 \div 2 = 45$ 日元，因此第一行输出 45。 顾客 2 购买商品所花费的金额为 $30 \div 2 + 20 \div 2 + 50 \div 2 = 50$ 日元，因此第二行输出 50。 顾客 3 购买商品所花费的金额为 $10 \div 2 + 40 \div 2 + 30 \div 2 + 20 \div 2 + 50 \div 2 = 75$ 日元，因此第三行输出 75。 该输入样例满足子任务 1、2、3、6 的约束。 ### 样例 2 解释 顾客 1 购买商品所花费的金额为 $40 + 30 + 20 \div 2 = 80$ 日元，因此第一行输出 80。 顾客 2 购买商品所花费的金额为 $30 + 20 + 50 \div 2 = 75$ 日元，因此第二行输出 75。 顾客 3 购买商品所花费的金额为 $10 + 40 + 30 \div 2 + 20 + 50 = 135$ 日元，因此第三行输出 135。 该输入样例满足子任务 1、3、6 的约束。 ### 数据范围 - $1 \le N \le 200\,000$。 - $1 \le M \le 200\,000$。 - $1 \le Q \le 200\,000$。 - $2 \le P_i \le 10^9$（$1 \le i \le N$）。 - $P_i$ 为偶数（$1 \le i \le N$）。 - $1 \le A_i \le M$（$1 \le i \le N$）。 - $1 \le T_k \le M$（$1 \le k \le Q$）。 - $1 \le L_k \le R_k \le N$（$1 \le k \le Q$）。 - 所有输入的值均为整数。 ### 子任务 1. （15 分）$N \le 2\,000$，$M \le 2\,000$，$Q \le 2\,000$。 2. （20 分）$M = 1$。 3. （12 分）$M \le 10$。 4. （14 分）$A_i \ne A_j$（$1 \le i < j \le N$）。 5. （22 分）$P_i = 2$（$1 \le i \le N$）。 6. （17 分）无额外约束。 翻译由 Qwen3-235B 完成。