A6543. 「CCO 2017」Vera 与现代艺术
编程题
提高+/省选-
知识点
题目描述
**译自 [CCO 2017](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2017/index.html) Day1 「[Vera and Modern Art](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2017/stage%202/day1.pdf)」**
在受到大画家毕加索的启发后， Vera 决定创造她的杰作。她有一张可以被简化成无限大的二维平面的画布。 Vera 喜欢 $2$ 的整数次幂 $(1,\, 2,\, 4,\, 8,\, 16,\, \ldots)$，并且将以 $2$ 的整数幂为步长给一些点染色。
Vera 将会染 $N$ 次，第 $i$ 次染色可以用三个整数 $x_i,\, y_i,\, v_i$ 描述。令 $a_i$ 为最大的不大于 $x_i$ 的 $2$ 的整数次幂， $b_i$ 为最大的不大于 $y_i$ 的 $2$ 的整数次幂， Vera 会用第 $v_i$ 种颜色在所有坐标满足 $(x_i + a_ip,\, y_i + b_iq)$ 的点上染色（$p,\, q$ 为非负整数）。一个点可以被不同的颜色分别染多次，也可以被同种颜色重复染多次，一个点的颜色为所有染过这个点的颜色之和。
接下来 Vera 将提出 $Q$ 个问题。对于第 $j$ 个问题，她希望知道坐标为 $(r_j,\, c_j)$ 的点是什么颜色。如果一个点没有被染过色，这个点的颜色就为 $0$。
因为你被迫做 Vera 的助手，你不得不回答 Vera 的问题。
在受到大画家毕加索的启发后， Vera 决定创造她的杰作。她有一张可以被简化成无限大的二维平面的画布。 Vera 喜欢 $2$ 的整数次幂 $(1,\, 2,\, 4,\, 8,\, 16,\, \ldots)$，并且将以 $2$ 的整数幂为步长给一些点染色。
Vera 将会染 $N$ 次，第 $i$ 次染色可以用三个整数 $x_i,\, y_i,\, v_i$ 描述。令 $a_i$ 为最大的不大于 $x_i$ 的 $2$ 的整数次幂， $b_i$ 为最大的不大于 $y_i$ 的 $2$ 的整数次幂， Vera 会用第 $v_i$ 种颜色在所有坐标满足 $(x_i + a_ip,\, y_i + b_iq)$ 的点上染色（$p,\, q$ 为非负整数）。一个点可以被不同的颜色分别染多次，也可以被同种颜色重复染多次，一个点的颜色为所有染过这个点的颜色之和。
接下来 Vera 将提出 $Q$ 个问题。对于第 $j$ 个问题，她希望知道坐标为 $(r_j,\, c_j)$ 的点是什么颜色。如果一个点没有被染过色，这个点的颜色就为 $0$。
因为你被迫做 Vera 的助手，你不得不回答 Vera 的问题。
输入格式
第一行包括两个整数 $N,\, Q$ ，用一个空格分隔。
接下来 $N$ 行，每行三个空格隔开的整数 $x_i,\, y_i,\, v_i$，表示用第 $v_i$ 种颜色进行题目中的染色操作，参数为 $x_i$ 和 $y_i$。
再接下来 $Q$ 行，每行两个空格隔开的整数 $r_j,\, c_j$，表示询问点 $(r_j,\, c_j)$ 的颜色。
接下来 $N$ 行，每行三个空格隔开的整数 $x_i,\, y_i,\, v_i$，表示用第 $v_i$ 种颜色进行题目中的染色操作，参数为 $x_i$ 和 $y_i$。
再接下来 $Q$ 行，每行两个空格隔开的整数 $r_j,\, c_j$，表示询问点 $(r_j,\, c_j)$ 的颜色。
输出格式
输出共有 $Q$ 行，每行一个整数，第 $j$ 行的整数表示点$(r_j,\, c_j)$ 的颜色。
输入输出样例
输入 #1
5 6 1 2 1 3 4 2 4 5 3 6 3 4 7 1 5 2 6 7 8 5 9 11 2 10 7 4 5
输出 #1
1 8 0 6 4 3
说明/提示
对于 $20\%$ 的数据， $N,\, Q\leqslant 2000$；
对于另外 $20\%$ 的数据， $y_i = 1(1\leqslant i\leqslant N)$；
对于另外 $20\%$ 的数据， $N,\, Q\leqslant 10^5$ 且 $1\leqslant r_j,\, c_j\leqslant 10^9(1\leqslant j\leqslant Q)$。
对于全部的数据， $1\leqslant N,\, Q\leqslant 2\cdot 10^5$，$i\leqslant i\leqslant N;\, 1\leqslant v_i\leqslant 10\, 000;\, 1\leqslant x_i,\, y_i\leqslant 10^{18}$，$1\leqslant j\leqslant Q;\, 1\leqslant r_j\leqslant 10^{18};\, 1\leqslant c_j\leqslant 10^{18}$。
**请注意在 LibreOJ 上共有 $5$ 个子任务，其中第一个子任务为样例。**
对于另外 $20\%$ 的数据， $y_i = 1(1\leqslant i\leqslant N)$；
对于另外 $20\%$ 的数据， $N,\, Q\leqslant 10^5$ 且 $1\leqslant r_j,\, c_j\leqslant 10^9(1\leqslant j\leqslant Q)$。
对于全部的数据， $1\leqslant N,\, Q\leqslant 2\cdot 10^5$，$i\leqslant i\leqslant N;\, 1\leqslant v_i\leqslant 10\, 000;\, 1\leqslant x_i,\, y_i\leqslant 10^{18}$，$1\leqslant j\leqslant Q;\, 1\leqslant r_j\leqslant 10^{18};\, 1\leqslant c_j\leqslant 10^{18}$。
**请注意在 LibreOJ 上共有 $5$ 个子任务，其中第一个子任务为样例。**