A22517.middle
省选/NOI-
官方
通过率:0%
时间限制:2.00s
内存限制:512MB
题目描述
一个长度为 n 的序列 a,设其排过序之后为 b,其中位数定义为 bn/2,其中 a,b 从 0 开始标号,除法下取整。
给你一个长度为 n 的序列 s。
回答 Q 个这样的询问:s 的左端点在 [a,b] 之间,右端点在 [c,d] 之间的子区间中,最大的中位数。
其中 a<b<c<d。
位置也从 0 开始标号。
我会使用一些方式强制你在线。
输入格式
第一行序列长度 n。
接下来 n 行按顺序给出 a 中的数。
接下来一行 Q。
然后 Q 行每行 a,b,c,d,我们令上个询问的答案是 x(如果这是第一个询问则 x=0)。
令数组 q={(a+x)modn,(b+x)modn,(c+x)modn,(d+x)modn}。
将 q 从小到大排序之后,令真正的要询问的 a=q0,b=q1,c=q2,d=q3。
输入保证满足条件。
输出格式
Q 行依次给出询问的答案。
输入输出样例
输入#1
5 170337785 271451044 22430280 969056313 206452321 3 3 1 0 2 2 3 1 4 3 1 4 0
输出#1
271451044 271451044 969056313
说明/提示
1≤n≤20000,1≤Q≤25000,1≤ai≤109。