#P2653. middle

    ID: 1708 传统题 1000ms 512MiB 尝试: 3054 已通过: 1090 难度: 8 上传者: 标签>CF2400提高+/省选-二分答案可持久化线段树路径复制离散化前后缀分解可持久化数据结构

middle

题目描述

一个长度为 nn 的序列 aa,设其排过序之后为 bb,其中位数定义为 b⌊n2⌋b_{\lfloor\frac{n}{2}\rfloor},其中 a,ba,b 从 00 开始标号,除法取下整。

给你一个长度为 nn 的序列 ss。

回答 QQ 个这样的询问:ss 的左端点在 [a,b][a,b] 之间,右端点在 [c,d][c,d] 之间的子区间中,最大的中位数。

其中 a<b<c<da<b<c<d。位置也从 00 开始标号。

强制在线。

输入格式

第一行序列长度 nn。

接下来 nn 行按顺序给出 aa 中的数。

接下来一行 QQ。

然后 QQ 行每行 a,b,c,da,b,c,d,我们令上个询问的答案是 xx(如果这是第一个询问则 x=0x=0)。

令数组 $q=\{(a+x)\bmod n,(b+x)\bmod n,(c+x)\bmod n,(d+x)\bmod n\}$。

将 qq 从小到大排序之后,令真正的要询问的 a=q0,b=q1,c=q2,d=q3a=q_0,b=q_1,c=q_2,d=q_3。

输入保证满足条件。

输出格式

QQ 行依次给出询问的答案。

样例

5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
271451044
271451044
969056313

数据范围与约定

对于 5%5\% 的数据, n,Q≤102n,Q \leq 10^2。

对于另 25%25\% 的数据, n≤2×103n \leq 2\times 10^3。

对于 100%100\% 的数据, n≤2×104n \leq 2\times 10^4,Q≤2.5×104Q \leq 2.5\times 10^4。