AT_joi2024_yo2_b 買い物 2 (Shopping 2)

JOI 商店里有 $N$ 个商品，每个商品编号为 $1$ 到 $N$。 每个商品都有“定价”和“种类”。第 $i$ 个商品（$1 \leq i \leq N$）的定价为 $P_i$ 日元。商品的种类用 $1$ 到 $M$ 之间的整数表示，第 $i$ 个商品的种类为 $A_i$。 JOI 商店决定举办促销活动。促销为期 $M$ 天，在第 $j$ 天（$1 \leq j \leq M$），所有种类为 $j$ 的商品都可以以定价的一半购入。 促销期间，会有 $Q$ 位顾客光临 JOI 商店。每位顾客编号为 $1$ 到 $Q$。第 $k$ 位顾客（$1 \leq k \leq Q$）会在促销的第 $T_k$ 天到店，购买商品 $L_k, L_k+1, \dots, 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 \leq k \leq Q$）输出第 $k$ 位顾客购买商品所需的金额（单位：日元，省略单位）。

## 小题目 1. （$15$ 分）$N \leq 2\,000$，$M \leq 2\,000$，$Q \leq 2\,000$。 2. （$20$ 分）$M = 1$。 3. （$12$ 分）$M \leq 10$。 4. （$14$ 分）$A_i \neq A_j$（$1 \leq i < j \leq N$）。 5. （$22$ 分）$P_i = 2$（$1 \leq i \leq N$）。 6. （$17$ 分）无额外限制。 ## 样例解释 1 第 $1$ 位顾客购买商品所需的金额为 $40 \div 2 + 30 \div 2 + 20 \div 2 = 45$ 日元，因此第 $1$ 行输出 $45$。 第 $2$ 位顾客购买商品所需的金额为 $30 \div 2 + 20 \div 2 + 50 \div 2 = 50$ 日元，因此第 $2$ 行输出 $50$。 第 $3$ 位顾客购买商品所需的金额为 $10 \div 2 + 40 \div 2 + 30 \div 2 + 20 \div 2 + 50 \div 2 = 75$ 日元，因此第 $3$ 行输出 $75$。 该输入样例满足小题目 $1,2,3,6$ 的限制。 ## 样例解释 2 第 $1$ 位顾客购买商品所需的金额为 $40 + 30 + 20 \div 2 = 80$ 日元，因此第 $1$ 行输出 $80$。 第 $2$ 位顾客购买商品所需的金额为 $30 + 20 + 50 \div 2 = 75$ 日元，因此第 $2$ 行输出 $75$。 第 $3$ 位顾客购买商品所需的金额为 $10 + 40 + 30 \div 2 + 20 + 50 = 135$ 日元，因此第 $3$ 行输出 $135$。 该输入样例满足小题目 $1,3,6$ 的限制。 ## 样例解释 3 该输入样例满足小题目 $1,3,4,6$ 的限制。 ## 样例解释 4 该输入样例满足小题目 $1,3,5,6$ 的限制。 ## 样例解释 5 该输入样例满足小题目 $1,3,6$ 的限制。 ## 数据范围 - $1 \leq N \leq 200\,000$。 - $1 \leq M \leq 200\,000$。 - $1 \leq Q \leq 200\,000$。 - $2 \leq P_i \leq 10^9$（$1 \leq i \leq N$）。 - $P_i$ 是偶数（$1 \leq i \leq N$）。 - $1 \leq A_i \leq M$（$1 \leq i \leq N$）。 - $1 \leq T_k \leq M$（$1 \leq k \leq Q$）。 - $1 \leq L_k \leq R_k \leq N$（$1 \leq k \leq Q$）。 - 所有输入的值均为整数。 由 ChatGPT 5 翻译