{"problem":{"name":"[NOIP2022] 比赛","description":{"content":"小 N 和小 O 会在 2022 年 11 月参加一场盛大的程序设计大赛 NOIP！小 P 会作为裁判主持竞赛。小 N 和小 O 各自率领了一支 $n$ 个人的队伍，选手在每支队伍内都是从 $1$ 到 $n$ 编号。每一个选手都有相应的程序设计水平。具体的，小 N 率领的队伍中，编号为 $i$（$1 \\leq i \\leq n$）的选手的程序设计水平为 $a _ i$；小 O 率领的队伍中，编号为","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8868"},"statements":[{"statement_type":"Markdown","content":"小 N 和小 O 会在 2022 年 11 月参加一场盛大的程序设计大赛 NOIP！小 P 会作为裁判主持竞赛。小 N 和小 O 各自率领了一支 $n$ 个人的队伍，选手在每支队伍内都是从 $1$ 到 $n$ 编号。每一个选手都有相应的程序设计水平。具体的，小 N 率领的队伍中，编号为 $i$（$1 \\leq i \\leq n$）的选手的程序设计水平为 $a _ i$；小 O 率领的队伍中，编号为 $i$（$1 \\leq i \\leq n$）的选手的程序设计水平为 $b _ i$。特别地，$\\{a _ i\\}$ 和 $\\{b _ i\\}$ 还分别构成了从 $1$ 到 $n$ 的排列。\n\n每场比赛前，考虑到路途距离，选手连续参加比赛等因素，小 P 会选择两个参数 $l, r$（$1 \\leq l \\leq r \\leq n$），表示这一场比赛会邀请两队中编号属于 $[l, r]$ 的所有选手来到现场准备比赛。在比赛现场，小 N 和小 O 会以掷骰子的方式挑选出参数 $p, q$（$l \\leq p \\leq q \\leq r$），只有编号属于 $[p, q]$ 的选手才能参赛。为了给观众以最精彩的比赛，两队都会派出编号在 $[p, q]$ 内的、程序设计水平值最大的选手参加比赛。假定小 N 派出的选手水平为 $m _ a$，小 O 派出的选手水平为 $m _ b$，则比赛的精彩程度为 $m _ a \\times m _ b$。\n\nNOIP 总共有 $Q$ 场比赛，每场比赛的参数 $l, r$ 都已经确定，但是 $p, q$ 还没有抽取。小 P 想知道，对于每一场比赛，在其所有可能的 $p, q$（$l \\leq p \\leq q \\leq r$）参数下的比赛的精彩程度之和。由于答案可能非常之大，你只需要对每一场答案输出结果对 $2 ^ {64}$ 取模的结果即可。\n\n## Input\n\n第一行包含两个正整数 $T, n$，分别表示测试点编号和参赛人数。如果数据为样例则保证 $T = 0$。\n\n第二行包含 $n$ 个正整数，第 $i$ 个正整数为 $a _ i$，表示小 N 队伍中编号为 $i$ 的选手的程序设计水平。\n\n第三行包含 $n$ 个正整数，第 $i$ 个正整数为 $b _ i$，表示小 O 队伍中编号为 $i$ 的选手的程序设计水平。\n\n第四行包含一个正整数 $Q$，表示比赛场数。\n\n接下来的 $Q$ 行，第 $i$ 行包含两个正整数 $l _ i, r _ i$，表示第 $i$ 场比赛的参数 $l, r$。\n\n## Output\n\n输出 $Q$ 行，第 $i$ 行包含一个非负整数，表示第 $i$ 场比赛中所有可能的比赛的精彩程度之和对 $2 ^ {64}$ 取模的结果。\n\n[samples]\n\n## Note\n\n**【样例 1 解释】**\n\n当 $p = 1, q = 2$ 的时候，小 N 会派出 $1$ 号选手，小 O 会派出 $2$ 号选手，比赛精彩程度为 $2 \\times 2 = 4$。\n\n当 $p = 1, q = 1$ 的时候，小 N 会派出 $1$ 号选手，小 O 会派出 $1$ 号选手，比赛精彩程度为 $2 \\times 1 = 2$。\n\n当 $p = 2, q = 2$ 的时候，小 N 会派出 $2$ 号选手，小 O 会派出 $2$ 号选手，比赛精彩程度为 $1 \\times 2 = 2$。\n\n**【样例 2】**\n\n该样例满足测试点 $1 \\sim 2$ 的限制。\n\n**【样例 3】**\n\n该样例满足测试点 $3 \\sim 5$ 的限制。\n\n**【数据范围】**\n\n对于所有数据，保证：$1 \\leq n, Q \\leq 2.5 \\times 10 ^ 5$，$1 \\leq l _ i \\leq r _ i \\leq n$，$1 \\leq a _ i, b _ i \\leq n$ 且 $\\{a _ i\\}$ 和 $\\{b _ i\\}$ 分别构成了从 $1$ 到 $n$ 的排列。\n\n::cute-table{tuack}\n\n| 测试点 | $n$ | $Q$ | 特殊性质 A | 特殊性质 B |\n| :----------: | :----------: | :----------: | :----------: | :----------: |\n| $1, 2$ | $\\leq 30$ | $\\leq 30$ | 是 | 是 |\n| $3, 4, 5$ | $\\leq 3,000$ | $\\leq 3,000$ | ^ | ^ |\n| $6, 7$ | $\\leq 10 ^ 5$ | $\\leq 5$ | ^ | ^ |\n| $8, 9$ | $\\leq 2.5 \\times 10 ^ 5$ | ^ | ^ | ^ |\n| $10, 11$ | $\\leq 10 ^ 5$ | ^ | 否 | 否 |\n| $12, 13$ | $\\leq 2.5 \\times 10 ^ 5$ | ^ | ^ | ^ |\n| $14, 15$ | $\\leq 10 ^ 5$ | $\\leq 10 ^ 5$ | 是 | 是 |\n| $16, 17$ | $\\leq 2.5 \\times 10 ^ 5$ | $\\leq 2.5 \\times 10 ^ 5$ | ^ | ^ |\n| $18, 19$ | $\\leq 10 ^ 5$ | $\\leq 10 ^ 5$ | ^ | 否 |\n| $20, 21$ | $\\leq 2.5 \\times 10 ^ 5$ | $\\leq 2.5 \\times 10 ^ 5$ | ^ | ^ |\n| $22, 23$ | $\\leq 10 ^ 5$ | $\\leq 10 ^ 5$ | 否 | ^ |\n| $24, 25$ | $\\leq 2.5 \\times 10 ^ 5$ | $\\leq 2.5 \\times 10 ^ 5$ | ^ | ^ |\n\n特殊性质 A：保证 $a$ 是均匀随机生成的 $1 \\sim n$ 的排列。\n\n特殊性质 B：保证 $b$ 是均匀随机生成的 $1 \\sim n$ 的排列。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8868","tags":["线段树","2022","NOIP 提高组","O2优化"],"sample_group":[["0 2\n2 1\n1 2\n1\n1 2","8"],["见附件下的 match/match2.in。","见附件下的 match/match2.ans。"],["见附件下的 match/match3.in。","见附件下的 match/match3.ans。"]],"created_at":"2026-03-03 11:09:25"}}