题目链接：P2839 [国家集训队]middle – 洛谷 – 计算机科学教育新生态

题意

中位数：给定一个长度为 $n$，下标从 $0$ 开始的序列 $a$，设其排序之后为 $b$，那么中位数为 $b_{\lfloor\frac{n}{2}\rfloor}$.

给定一个长度为 $n$ 的，下标从 $0$ 开始的序列 $s$，回答 $Q$ 次形如 $(a, b, c, d)$ 的询问，表示：

保证 $a_i<b_i<c_i<d_i$，多测，强制在线。

$1\leq n\leq 20000$，$1\leq Q\leq 25000$.

分析

由于中位数的定义中，下标从 $0$ 开始，一些细节问题需要特别考虑。

对于一个 $x$，把 $>=x$ 的元素赋值为 $1$，否则赋值为 $-1$。则区间元素和 $>=0$，当且仅当中位数 $\operatorname{mid}>=x$.

考虑对每次询问二分。

在处理询问之前，对于每个 $x$ 预处理出一颗线段树，维护区间内的最大前缀、最大后缀、区间元素和。

在询问 $(a,b,c,d)$ 中，$[b+1,c]$ 这段是必须选的，再加上 $[a, b]$ 中的最大后缀，和 $[c,d]$ 中的最大前缀即可。

注意到离散化后，每当 $x$ 的值增加 $1$ 时，只会影响序列中的一个值，因此建立可持久化线段树。

$x$ 每增加 $1$，线段树只会多加一条链，空间复杂度为 $\mathcal{O}(Q\log n)$ 级别。

代码

不难实现。

const int MAXN = 20010, inf = 0x3f3f3f3f3f3f3f3f;
int n;
struct Node{
    int v, pos;
} a[MAXN];
bool cmp(Node A, Node B) { return A.v < B.v; }
struct Point{ //可持久化线段树
    int lv, rv, sum; //区间内最大前缀和，最大后缀和，区间元素和
    int lc, rc; //左右儿子编号
} t[MAXN << 5];
int root[MAXN], p_cnt = 0;
#define ls(x) (t[x].lc)
#define rs(x) (t[x].rc)
void push_up(int rt) {
    t[rt].sum = t[ls(rt)].sum + t[rs(rt)].sum;
    t[rt].lv = max(t[ls(rt)].lv, t[ls(rt)].sum + t[rs(rt)].lv);
    t[rt].rv = max(t[rs(rt)].rv, t[rs(rt)].sum + t[ls(rt)].rv);
}
void build(int &rt, int l, int r) {
    rt = ++p_cnt;
    if(l == r) {
        //初始的 x = 0，所以每个点权值都是 1
        t[rt].lv = t[rt].rv = t[rt].sum = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(rt), l, mid);
    build(rs(rt), mid + 1, r);
    push_up(rt);
}
void update(int &rt, int his, int l, int r, int x, int v) {
    //以 his 为基础进行修改，把 x -> v
    rt = ++p_cnt; t[rt] = t[his];
    if(l == r) {
        t[rt].lv = t[rt].rv = t[rt].sum = v;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) update(ls(rt), ls(his), l, mid, x, v);
    else update(rs(rt), rs(his), mid + 1, r, x, v);
    push_up(rt);
}
int query_s(int rt, int l, int r, int x, int y) {
    //询问区间[x ,y]的和
    if(x <= l && r <= y) return t[rt].sum;
    int mid = (l + r) >> 1, ret = 0;
    if(x <= mid) ret += query_s(ls(rt), l, mid, x, y);
    if(y > mid) ret += query_s(rs(rt), mid + 1, r, x, y);
    return ret;
}
int query_l(int rt, int l, int r, int x, int y) {
    //询问区间[x, y]最大的前缀和
    if(x <= l && r <= y) return t[rt].lv;
    int mid = (l + r) >> 1;
    if(y <= mid) return query_l(ls(rt), l, mid, x, y); //注意要分类讨论
    else if(x > mid) return query_l(rs(rt), mid + 1, r, x, y);
    else return max(
        query_l(ls(rt), l, mid, x, mid), 
        query_s(ls(rt), l, mid, x, mid) + query_l(rs(rt), mid + 1, r, mid + 1, y)
    );
}
int query_r(int rt, int l, int r, int x, int y) {
    //询问区间[x, y]最大的后缀和
    if(x <= l && r <= y) return t[rt].rv;
    int mid = (l + r) >> 1;
    if(y <= mid) return query_r(ls(rt), l, mid, x, y);
    else if(x > mid) return query_r(rs(rt), mid + 1, r, x, y);
    else return max(
        query_r(rs(rt), mid + 1, r, mid + 1, y), 
        query_s(rs(rt), mid + 1, r, mid + 1, y) + query_r(ls(rt), l, mid, x, mid)
    );
}
bool check(int x, int a, int b, int c, int d) {
    //是否存在端点 a<=l<=b, c<=r<=d 满足 [l, r] 的元素和 >= 0
    int sum = 0;
    if(c >= b + 2) { //b, c中间有一段一定要选
        sum += query_s(root[x], 1, n, b + 1, c - 1);
    }
    sum += query_r(root[x], 1, n, a, b); //后缀 最大连续段
    sum += query_l(root[x], 1, n, c, d); //前缀 最大连续段
    return (sum >= 0);
}
signed main() {
    n = read();
    for(int i = 1; i <= n; i++) a[i].v = read(), a[i].pos = i;
    sort(a + 1, a + n + 1, cmp); //离散化
    build(root[1], 1, n);
    for(int i = 2; i <= n + 1; i++) {
        update(root[i], root[i - 1], 1, n, a[i - 1].pos, -1);
    }
    int Q = read(), lstans = 0;
    while(Q--) {
        int q[4];
        q[0] = (read() + lstans) % n + 1;
        q[1] = (read() + lstans) % n + 1;
        q[2] = (read() + lstans) % n + 1;
        q[3] = (read() + lstans) % n + 1;
        sort(q, q + 4);
        int l = 1, r = n, mid, ans = -1;
        while(l <= r) {
            mid = (l + r) >> 1;
            if(check(mid, q[0], q[1], q[2], q[3])) {
                l = mid + 1;
                ans = mid;
            } else r = mid - 1;
        }
        printf("%lld\n", a[ans].v); lstans = a[ans].v;
    }
    return 0;
}