P6787: 比赛（match）
传统题
2.000s
时间限制
512MB
内存限制
8 提交
0 解决
【题目描述】
【题目描述】
小 N
和小 O
会在 2022
年 11
月参加一场盛大的程序设计大赛 NOIP!
小 P
会作为裁判主持竞赛。小 N
和小 O
各自率领了一支 n 个人的队伍，选手在每支队伍内都是从1
到 n
编号。每一个选手都有相应的程序设计水平。具体的，小 N
率领的队伍中，编号为 i (1 ≤ i ≤ n)
的选手的程序设计水平为 ai
；小 O
率领的队伍中，编号为 i (1 ≤ i ≤ n)
的选手的程序设计水平为 bi。特别地，{ai}
和 {bi}
还分别构成了从 1
到 n
的排列。
每场比赛前，考虑到路途距离，选手连续参加比赛等因素，小 P 会选择两个参数l, r (1 ≤ l ≤ r ≤ n)
，表示这一场比赛会邀请两队中编号属于 [l, r]
的所有选手来到现场准备比赛。在比赛现场，小 N
和小 O
会以掷骰子的方式挑选出参数 p, q (l ≤ p ≤ q ≤ r)
，只有编号属于 [p, q]
的选手才能参赛。为了给观众以最精彩的比赛，两队都会派出编号
在 [p, q]
内的、程序设计水平值最大的选手参加比赛。假定小 N
排出的选手水平为 ma
，小 O
派出的选手水平为 mb
，则比赛的精彩程度为 ma × mb
。
NOIP
总共有 Q
场比赛，每场比赛的参数 l, r
都已经确定，但是 p, q
还没有抽取。小 P
想知道，对于每一场比赛，在其所有可能的 p, q (l ≤ p ≤ q ≤ r)
参数下比赛的精彩程度之和。由于答案可能非常之大，你只需要对每一场比赛输出答案对 2
^64
取模的结果即可。
【输入格式】
从文件 match.in
中读入数据。
第一行包含两个正整数 T, n
，分别表示测试点编号和参赛人数。如果数据为样例则保证 T = 0
。
第二行包含 n
个正整数，第 i
个正整数为 ai
，表示小 N
队伍中编号为 i
的选手的程序设计水平。
第三行包含 n
个正整数，第 i
个正整数为 bi
，表示小 O
队伍中编号为 i
的选手的程序设计水平。
第四行包含一个正整数 Q
，表示比赛场数。
接下来的 Q
行，第 i
行包含两个正整数 li, ri
，表示第 i
场比赛的参数 l, r
。
【输出格式】
输出到文件 match.out
中。
输出 Q
行，第 i
行包含一个非负整数，表示第 i
场比赛中所有可能的比赛的精彩程度之和对 2
^64
取模的结果。
【样例 1
输入】
0 2
2 1
1 2
1
1 2
【样例 1
输出】
8
【样例 1
解释】
当 p = 1, q = 2
的时候，小 N
会派出 1
号选手，小 O
会派出 2
号选手，比赛精彩程度为 2 × 2 = 4
。
当 p = 1, q = 1
的时候，小 N
会派出 1
号选手，小 O
会派出 1
号选手，比赛精彩程度为 2 × 1 = 2
。
当 p = 2, q = 2
的时候，小 N
会派出 2
号选手，小 O
会派出 2
号选手，比赛精彩程度为 1 × 2 = 2.
【样例 2
】
见选手目录下的 match/match2.in
与 match/match2.ans
。
该样例满足测试点 1 ∼ 2
的限制。
【样例 3
】
见选手目录下的 match/match3.in
与 match/match3.ans
。
该样例满足测试点 3 ∼ 5
的限制。
【子任务】
对于所有数据，保证：1 ≤ n, Q ≤ 2.5 × 10
^5，1 ≤ li ≤ ri ≤ n，1 ≤ ai, bi ≤ n
且 {ai}
和 {bi}
分别构成了从 1
到 n 的排列。
测试点
|
n
|
Q
|
特殊性质 A
|
特殊性质 B
|
1,2
|
≤ 30
|
≤ 30
|
是
|
是
|
3,4,5
|
≤ 3000
|
≤5
|
6,7
|
≤ 10^5
|
8,9
|
≤ 2.5×10^5
|
10,11
|
≤ 10^5
|
否
|
否
|
12,13
|
≤ 2.5×10^5
|
14,15
|
≤ 10^5
|
≤ 10^5
|
是
|
是
|
16,17
|
≤ 2.5×10^5
|
≤ 2.5×10^5
|
18,19
|
≤ 10^5
|
≤ 10^5
|
否
|
20,21
|
≤ 2.5×10^5
|
≤ 2.5×10^5
|
22,23
|
≤ 10^5
|
≤ 10^5
|
否
|
24,25
|
≤ 2.5×10^5
|
≤ 2.5×10^5
|
特殊性质 A:
保证 a
是均匀随机生成的 1 ∼ n
的排列。
特殊性质 B:
保证 b
是均匀随机生成的 1 ∼ n 的排列。