(mathcal{Description})
Link.
给定序列 ({a_n})，(q) 组询问，给定 (a<b<c<d)，求 (lle[a,b],rle[c,d]) 的子序列 ([l,r]) 的中位数最大值。若长度为偶数，中位数取中间两数较大的一个。强制在线。
(nle2 imes10^4)，(qle2.5 imes10^4)。
(mathcal{Solution})
crashed：众所周知，中位数是可以二分的。
考虑单组询问，二分中位数 (mid)，把序列中大于等于 (mid) 的值设为 (1)，小于 (mid) 的值设为 (0)，求出满足条件的 ([l,r]) 的序列和的最大值。若最大值是非负数，表明 (mid) 可行，且还能增大；否则只能减少。
多组询问，发现对于每个 (mid)，序列的长相都不尽相同。但序列的变化是极其有限的——当 (mid) 递增，每个位置只会又 (1) 变为 (0) 一次。
由此可以想到主席树。离散化之后，预处理 (mid=1,2,dots,n) 时的序列，建成主席树。树上维护区间和，区间最大前缀，区间最大后缀。处理询问时仍二分 (mid)，利用以 (mid) 为根的这棵权值线段树的信息，求出区间最大和。显然最大和为 ([a,b) ext{最大后缀}+[b,c] ext{之和}+(c,d] ext{最大前缀})，判断正负情况即可。由于二分时答案会尽量靠右，而最大的答案一定恰好是序列中的某个值，所以不必担心答案不在序列中的情况。
复杂度 (mathcal O(nlog^2n))。
(mathcal{Code})
#include <cstdio>
#include <vector>
#include <algorithm>
typedef std::pair<int, int> pii;
const int MAXN = 20000;
int n, a[MAXN + 5], tval[MAXN + 5], root[MAXN + 5];
std::vector<int> apr[MAXN + 5];
inline int rint () {
int x = 0; char s = getchar ();
for ( ; s < '0' || '9' < s; s = getchar () );
for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
return x;
}
inline int max_ ( const int a, const int b ) { return a < b ? b : a; }
struct PersistentSegmentTree {
static const int MAXND = MAXN * 40;
int cntnd, ch[MAXND + 5][2], sum[MAXND + 5], lmx[MAXND + 5], rmx[MAXND + 5];
inline void pushup ( const int rt ) {
sum[rt] = sum[ch[rt][0]] + sum[ch[rt][1]];
lmx[rt] = max_ ( lmx[ch[rt][0]], sum[ch[rt][0]] + lmx[ch[rt][1]] );
rmx[rt] = max_ ( rmx[ch[rt][1]], sum[ch[rt][1]] + rmx[ch[rt][0]] );
}
inline void build ( int& rt, const int l, const int r ) {
rt = ++ cntnd;
if ( l == r ) return sum[rt] = lmx[rt] = rmx[rt] = 1, void ();
int mid = l + r >> 1;
build ( ch[rt][0], l, mid ), build ( ch[rt][1], mid + 1, r );
pushup ( rt );
}
inline void update ( int& rt, const int l, const int r, const int x ) {
int old = rt; rt = ++ cntnd;
ch[rt][0] = ch[old][0], ch[rt][1] = ch[old][1];
sum[rt] = sum[old], lmx[rt] = lmx[old], rmx[rt] = rmx[old];
if ( l == r ) return sum[rt] = -1, lmx[rt] = rmx[rt] = 0, void ();
int mid = l + r >> 1;
if ( x <= mid ) update ( ch[rt][0], l, mid, x );
else update ( ch[rt][1], mid + 1, r, x );
pushup ( rt );
}
inline int qrySum ( const int rt, const int l, const int r, const int ql, const int qr ) {
if ( ql <= l && r <= qr ) return sum[rt];
int mid = l + r >> 1, ret = 0;
if ( ql <= mid ) ret += qrySum ( ch[rt][0], l, mid, ql, qr );
if ( mid < qr ) ret += qrySum ( ch[rt][1], mid + 1, r, ql, qr );
return ret;
}
inline pii qryLmx ( const int rt, const int l, const int r, const int ql, const int qr ) {
if ( ql <= l && r <= qr ) return { lmx[rt], sum[rt] };
int mid = l + r >> 1, ret = 0, s = 0; pii tmp;
if ( ql <= mid ) {
tmp = qryLmx ( ch[rt][0], l, mid, ql, qr );
ret = tmp.first, s = tmp.second;
}
if ( mid < qr ) {
tmp = qryLmx ( ch[rt][1], mid + 1, r, ql, qr );
ret = max_ ( ret, s + tmp.first ), s += tmp.second;
}
return { ret, s };
}
inline pii qryRmx ( const int rt, const int l, const int r, const int ql, const int qr ) {
if ( ql <= l && r <= qr ) return { rmx[rt], sum[rt] };
int mid = l + r >> 1, ret = 0, s = 0; pii tmp;
if ( mid < qr ) {
tmp = qryRmx ( ch[rt][1], mid + 1, r, ql, qr );
ret = tmp.first, s = tmp.second;
}
if ( ql <= mid ) {
tmp = qryRmx ( ch[rt][0], l, mid, ql, qr );
ret = max_ ( ret, s + tmp.first ), s += tmp.second;
}
return { ret, s };
}
} pst;
int main () {
n = rint ();
for ( int i = 1; i <= n; ++ i ) a[i] = tval[i] = rint ();
std::sort ( tval + 1, tval + n + 1 );
int lim = std::unique ( tval + 1, tval + n + 1 ) - tval - 1;
for ( int i = 1; i <= n; ++ i ) {
a[i] = std::lower_bound ( tval + 1, tval + lim + 1, a[i] ) - tval;
apr[a[i]].push_back ( i );
}
pst.build ( root[1], 1, n ); // 注意这里n的意义成为了序列长度，不要与lim搞混。
for ( int i = 2; i <= lim; ++ i ) {
root[i] = root[i - 1];
for ( int p: apr[i - 1] ) pst.update ( root[i], 1, n, p );
}
for ( int q = rint (), ans = 0, tmp[4]; q --; ) {
for ( int i = 0; i < 4; ++ i ) tmp[i] = ( rint () + ans ) % n + 1;
std::sort ( tmp, tmp + 4 );
int l = 1, r = lim;
while ( l <= r ) {
int mid = l + r >> 1;
int cnt = pst.qrySum ( root[mid], 1, n, tmp[1], tmp[2] )
+ pst.qryLmx ( root[mid], 1, n, tmp[2] + 1, tmp[3] ).first
+ pst.qryRmx ( root[mid], 1, n, tmp[0], tmp[1] - 1 ).first;
if ( cnt >= 0 ) l = ( ans = mid ) + 1;
else r = mid - 1;
}
printf ( "%d
", ans = tval[ans] );
}
return 0;
}