3929. T3-[NOIP2022] 比赛(contest)
时间限制：2000 MS 内存限制：512 MB
题目描述
小 $ N $ 和小 $ O $ 会在 $ 2022 $ 年 $ 11 $ 月参加一场盛大的程序设计大赛 $ NOIP $ 。 小 $ P $ 会作为裁判主持竞赛。 小 $ N $ 和小 $ O $ 各自率领了一支 $ n $ 个人的队伍，选手在每支队伍内都是从 $ 1 $ 到 $ n $ 编号。 每一个选手都有相应的程序设计水平。 具体的，小 $ N $ 率领的队伍中，编号为 $ i $ ( $ 1≤i≤n $ ) 的选手的程序设计水平为 $ a_i $ ；小 $ O $ 率领的队伍中，编号为 $ i $ ( $ 1≤i≤n $ ) 的选手的程序设计水平为 $ b_i $ 。 特别地， $ {a_i} $ 和 $ {b_i} $ 还分别构成了从 $ 1 $ 到 $ n $ 的排列。 每场比赛前，考虑到路途距离，选手连续参加比赛等因素，小 $ P $ 会选择两个参数 $ l,r $ ( $ 1≤l≤r≤n $ )，表示这一场比赛会邀请两队中编号属于 $ [l,r] $ 的所有选手来到现场准备比赛。 在比赛现场，小 $ N $ 和小 $ O $ 会以掷骰子的方式挑选出参数 $ p,q $ ( $ l≤p≤q≤r $ )，只有编号属于 $ [p,q] $ 的选手才能参赛。 为了给观众以最精彩的比赛，两队都会派出编号在 $ [p,q] $ 内的、程序设计水平值最大的选手参加比赛。 假定小 $ N $ 排出的选手水平为 $ m_a $ ，小 $ O $ 派出的选手水平为 $ m_b $ ，则比赛的精彩程度为 $ m_a×m_b $ 。 $ NOIP $ 总共有 $ Q $ 场比赛，每场比赛的参数 $ l,r $ 都已经确定，但是 $ p,q $ 还没有抽取。 小 $ P $ 想知道，对于每一场比赛，在其所有可能的 $ p,q $ ( $ l≤p≤q≤r $ ) 参数下比赛的精彩程度之和。 由于答案可能非常之大，你只需要对每一场比赛输出答案对 $ 2^{64} $ 取模的结果即可。 #### 输入格式 第一行包含两个正整数 $ T,n $ ，分别表示测试点编号和参赛人数。如果数据为样例则保证 $ T=0 $ 。 第二行包含 $ n $ 个正整数，第 $ i $ 个正整数为 $ a_i $ ，表示小 $ N $ 队伍中编号为 $ i $ 的选手的程序设计水平。 第三行包含 $ n $ 个正整数，第 $ i $ 个正整数为 $ b_i $ ，表示小 $ O $ 队伍中编号为 $ i $ 的选手的程序设计水平。 第四行包含一个正整数 $ Q $ ，表示比赛场数。 接下来的 $ Q $ 行，第 $ i $ 行包含两个正整数 $ l_i,r_i $ ，表示第 $ i $ 场比赛的参数 $ l,r $ 。 #### 输出格式 输出 $ Q $ 行，第 $ i $ 行包含一个非负整数，表示第 $ i $ 场比赛中所有可能的比赛的精彩程度之和对 $ 264 $ 取模的结果。 #### 数据范围 对于所有数据，保证： $ 1≤n,Q≤2.5×10^5 $ ， $ 1≤l_i≤r_i≤n $ ，$1≤a_i$,$b_i≤n$ $ 且 $ {$a_i$} $ 和 $ {$b_i$} $ 分别构成了从 $ $1$ $ 到 $ $n$ 的排列。  特殊性质 $ A $ : 保证 $ a $ 是均匀随机生成的 $ 1∼n $ 的排列。 特殊性质 $ B $ : 保证 $ b $ 是均匀随机生成的 $ 1∼n $ 的排列。 #### 输入样例： ``` 0 2 2 1 1 2 1 1 2 ``` #### 输出样例： ``` 8 ``` #### 样例解释 当 $ 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 $ 。