{"problem":{"name":"[Ynoi2003] 博丽灵梦","description":{"content":"矩形颜色数，带权。 给定一个有 $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$ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":7500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8530"},"statements":[{"statement_type":"Markdown","content":"矩形颜色数，带权。\n\n给定一个有 $n$ 个点的二维平面，每个点坐标为 $(i,p_i)$ ，其有权值 $a$。\n\n给定一个长为 $n$ 的数组 $b$，其下标从 $1$ 到 $n$。\n\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## Input\n\n第一行一个整数 $n$。\n\n接下来一行 $n$ 个数，第 $i$ 个数表示 $p_i$。\n\n接下来一行 $n$ 个数，第 $i$ 个数表示 $a_i$。\n\n接下来一行 $n$ 个数，第 $i$ 个数表示 $b_i$。\n\n接下来一行一个整数 $m$。\n\n接下来 $m$ 行，每行 $4$ 个数分别表示 $l_1,r_1,l_2,r_2$，是一组询问。\n\n## Output\n\n对每个询问，输出一行，包含一个整数，表示答案，答案对 $2^{32}$ 进行取模后输出。\n\n[samples]\n\n## Note\n\nIdea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078\n\n### 样例解释\n\n对于答案为 $27$ 的询问，$S=\\{1,4,5,9\\}$，对应 $b_j=9,4,5,9$，和为 $27$。\n\n对于答案为 $22$ 的询问，$S=\\{1,4,9\\}$，对应 $b_j=9,4,9$，和为 $22$。\n\n对于答案为 $4$ 的询问， $S=\\{4\\}$，对应 $b_j=4$，和为 $4$。\n\n对于答案为 $0$ 的询问， $S=\\emptyset$，和为 $0$。\n\n### 数据范围\n\n每个测试点的具体限制见下表：\n\n| 测试点编号  |     $n\\le $      |     $m\\le $      |  特殊限制  |\n| :---------: | :--------------: | :--------------: | :--------: |\n|     $1$     |       $10$       |       $10$       |     无     |\n|     $2$     |  $5\\times 10^3$  |  $5\\times 10^3$  |     无     |\n|     $3$     | $2.5\\times 10^4$ |  $5\\times 10^4$  | $\\text{A}$ |\n|     $4$     |  $5\\times 10^4$  |      $10^5$      | $\\text{A}$ |\n|     $5$     | $7.5\\times 10^4$ | $1.5\\times 10^5$ | $\\text{A}$ |\n|     $6$     |      $10^5$      |  $2\\times 10^5$  | $\\text{A}$ |\n|     $7$     |  $2\\times 10^4$  |  $2\\times 10^4$  |     无     |\n|     $8$     |  $3\\times 10^4$  |  $6\\times 10^4$  |     无     |\n|     $9$     |  $4\\times 10^4$  |  $8\\times 10^4$  |     无     |\n|    $10$     |  $5\\times 10^4$  |      $10^5$      |     无     |\n|    $11$     |  $6\\times 10^4$  | $1.2\\times 10^5$ |     无     |\n|    $12$     |  $7\\times 10^4$  | $1.4\\times 10^5$ |     无     |\n| $13\\sim 15$ |      $10^5$      |  $2\\times 10^5$  | $\\text{C}$ |\n| $16\\sim 18$ |      $10^5$      |  $2\\times 10^5$  |     无     |\n|    $19$     |      $10^5$      |  $3\\times 10^5$  |     无     |\n|    $20$     |      $10^5$      |  $4\\times 10^5$  |     无     |\n|    $21$     |      $10^5$      |  $5\\times 10^5$  |     无     |\n|    $22$     |      $10^5$      |  $6\\times 10^5$  |     无     |\n|    $23$     |      $10^5$      |  $8\\times 10^5$  |     无     |\n|    $24$     |      $10^5$      |      $10^6$      |     无     |\n|    $25$     |      $10^5$      |      $10^6$      |     无     |\n\n为了方便，下面记 $(a, b) \\leq (c, d)$ 表示平面上两个点 $(a, b),(c, d)$ 满足 $a \\leq c, b \\leq d$。\n\n特殊限制 A：对于所有询问有 $l_2 = 1, r_2 = n$。\n\n特殊限制 B：这个特殊限制太容易造水了，不要了。\n\n特殊限制 C：最多有 $50$ 对二元组 $(i, j)(1 \\leq i < j \\leq n)$ 不满足 $(i, p_i) \\leq (j, p_j)$。\n\n对于所有测试点：$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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8530","tags":["2003","O2优化","Ynoi"],"sample_group":[["9\n9 8 7 6 2 4 5 3 1\n1 1 4 5 1 4 1 9 1\n9 1 1 4 5 1 4 1 9\n9\n4 9 3 6\n2 9 1 8\n3 8 2 4\n3 9 2 7\n2 8 1 6\n1 9 1 9\n1 3 5 7\n2 3 3 3\n6 6 6 6","27\n27\n22\n27\n27\n27\n4\n0\n0"]],"created_at":"2026-03-03 11:09:25"}}