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 翻译