博丽灵梦 - المسألة

矩形颜色数，带权。

给定一个有 $n$ 个点的二维平面，每个点坐标为 $(i,p_i)$ ，其有权值 $a$。

给定一个长为 $n$ 的数组 $b$，其下标从 $1$ 到 $n$。

有 $m$ 次查询，每次查询给定一个矩形 $l_1,r_1,l_2,r_2$，定义集合 $S=\{a_i|l_1\le i\le r_1 \land l_2\le p_i\le r_2\}$，求对于集合 $S$ 中所有元素 $j$，$b_j$ 的和。

第一行一个整数 $n$。

接下来一行 $n$ 个数，第 $i$ 个数表示 $p_i$。

接下来一行 $n$ 个数，第 $i$ 个数表示 $a_i$。

接下来一行 $n$ 个数，第 $i$ 个数表示 $b_i$。

接下来一行一个整数 $m$。

接下来 $m$ 行，每行 $4$ 个数分别表示 $l_1,r_1,l_2,r_2$，是一组询问。

对每个询问，输出一行，包含一个整数，表示答案，答案对 $2^{32}$ 进行取模后输出。

9
9 8 7 6 2 4 5 3 1
1 1 4 5 1 4 1 9 1
9 1 1 4 5 1 4 1 9
9
4 9 3 6
2 9 1 8
3 8 2 4
3 9 2 7
2 8 1 6
1 9 1 9
1 3 5 7
2 3 3 3
6 6 6 6

对于答案为 $27$ 的询问，$S=\{1,4,5,9\}$，对应 $b_j=9,4,5,9$，和为 $27$。

对于答案为 $22$ 的询问，$S=\{1,4,9\}$，对应 $b_j=9,4,9$，和为 $22$。

对于答案为 $4$ 的询问， $S=\{4\}$，对应 $b_j=4$，和为 $4$。

对于答案为 $0$ 的询问， $S=\emptyset$，和为 $0$。

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

每个测试点的具体限制见下表：

测试点编号	$n\le $	$m\le $	特殊限制
$1$	$10$	$10$	无
$2$	$5\times 10^3$	$5\times 10^3$	无
$3$	$2.5\times 10^4$	$5\times 10^4$	$\text{A}$
$4$	$5\times 10^4$	$10^5$	$\text{A}$
$5$	$7.5\times 10^4$	$1.5\times 10^5$	$\text{A}$
$6$	$10^5$	$2\times 10^5$	$\text{A}$
$7$	$2\times 10^4$	$2\times 10^4$	无
$8$	$3\times 10^4$	$6\times 10^4$	无
$9$	$4\times 10^4$	$8\times 10^4$	无
$10$	$5\times 10^4$	$10^5$	无
$11$	$6\times 10^4$	$1.2\times 10^5$	无
$12$	$7\times 10^4$	$1.4\times 10^5$	无
$13\sim 15$	$10^5$	$2\times 10^5$	$\text{C}$
$16\sim 18$	$10^5$	$2\times 10^5$	无
$19$	$10^5$	$3\times 10^5$	无
$20$	$10^5$	$4\times 10^5$	无
$21$	$10^5$	$5\times 10^5$	无
$22$	$10^5$	$6\times 10^5$	无
$23$	$10^5$	$8\times 10^5$	无
$24$	$10^5$	$10^6$	无
$25$	$10^5$	$10^6$	无

为了方便，下面记 $(a, b) \leq (c, d)$ 表示平面上两个点 $(a, b),(c, d)$ 满足 $a \leq c, b \leq d$。

特殊限制 A：对于所有询问有 $l_2 = 1, r_2 = n$。

特殊限制 B：这个特殊限制太容易造水了，不要了。

特殊限制 C：最多有 $50$ 对二元组 $(i, j)(1 \leq i < j \leq n)$ 不满足 $(i, p_i) \leq (j, p_j)$。

对于所有测试点：$2 \leq n \leq 10^5$，$1 \leq m \leq 10^6$，$1 \leq l_1\le r_1 \leq n$，$1 \leq l_2\le r_2 \leq n$，保证 $p_i$ 为一个排列，保证 $1\le p_i,a_i,b_i\le n$。

QOJ.ac