配点: 100 点
問題文
JOI商店 有 N 个产品,产品包括 它们的编号最大为 1 它们的编号最大为 N 。
每个产品包括:定価和種類已定义。产品展示 i (1 \leqq i \leqq N) 的标价为 P_i 这是一个圆圈。产品类型是 1 以上 M 用下面的整数表示,乘积 i (1 \leqq i \leqq N)类型是 A_i 。从
JOI Shop 决定进行促销。销售是 M 持续数天,j 日目 (1 \leqq j \leqq M) 是类型 您可以以正常价格的一半购买所有 j 产品。
促销期间,Q 顾客参观了JOI商店。对于客户 它们的编号最大为 1 它们的编号最大为 Q 。顾客 k (1 \leqq k \leqq Q)正在销售。 T_k 当天参观了JOI商店并购买了产品。 L_k, L_k+1, \dots, R_k 的 1 我一件一件地买了。
为了调查销售效果,我想知道每个客户购买产品所花费的金额。
给定产品信息和客户信息,编写一个程序来计算每个客户购买该产品所需的金额。
制約
- 1 \leqq N \leqq 200\,000.
- 1 \leqq M\leqq 200\,000.
- 1 \leqq Q \leqq 200\,000.
- 2 \leqq P_i \leqq 10^9 (1 \leqq i \leqq N).
- P_i 是偶数 (1 \leqq i \leqq N).
- 1 \leqq A_i \leqq M (1 \leqq i \leqq N).
- 1 \leqq T_k \leqq M (1 \leqq k \leqq Q).
- 1 \leqq L_k \leqq R_k \leqq N (1 \leqq k \leqq Q).
- 所有输入值都是整数。
小課題
- (15 点) N \leqq 2\,000,M \leqq 2\,000,Q \leqq 2\,000.
- (20 点) M = 1.
- (12 点) M \leqq 10.
- (14 点) A_i \neq A_j (1 \leqq i < j \leqq N).
- (22 点) P_i = 2 (1 \leqq i \leqq N).
- (17 点)没有额外的限制。
入力
输入按以下格式给出。 输出
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 \leqq k \leqq Q) 有一位客户 输出购买该产品所需花费的金额 k ,省略单位(日元)。 购买该产品的费用为
入力例 1
5 1 3 10 1 40 1 30 1 20 1 50 1 1 2 4 1 3 5 1 1 5
出力例 1
45 50 75
客 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
5 3 3 10 1 40 3 30 2 20 1 50 3 1 2 4 3 3 5 2 1 5
出力例 2
80 75 135
客 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
5 5 3 50 2 70 4 20 5 30 1 10 3 4 2 4 5 1 5 2 3 4
出力例 3
85 170 50
此输入示例是一个小作业。 1,3,4,6 满足约束。
入力例 4
10 5 4 2 1 2 5 2 4 2 3 2 4 2 2 2 2 2 4 2 2 2 1 3 2 7 1 1 7 2 1 10 5 5 8
出力例 4
11 13 17 8
此输入示例是一个小作业。 1,3,5,6 满足约束。
入力例 5
10 10 10 741703628 7 231838922 5 920286164 3 763741914 5 246151406 7 54109256 1 966457488 5 441379880 10 458514202 2 224373612 1 5 5 10 2 2 7 1 9 9 1 3 4 9 4 6 1 1 7 9 4 7 4 8 8 7 5 9 1 4 5
出力例 5
1907757100 3182585150 458514202 1684028078 1064002576 3897234150 2030460064 441379880 2043536529 1009893320
此输入示例是一个小作业。 1,3,6 满足约束。