mxqz 样例过但 0pts 有错误数据 悬很多关

以后再也不写分块了 /kk

#include <bits/stdc++.h>
using namespace std;

const int N = 2e4 + 5, M = 150;
int n, a[N], Q; int len, b[N];
int lst, q[5];

int o(int i, int x) { return a[i] < x ? -1 : 1; }
namespace ArrayDiv {
    int B, tot, L[M], R[M], bel[N];
    int sum[M][N], pre[M][N], suf[M][N];
    void init() {
        memset(sum, -0x3f, sizeof sum); memset(pre, -0x3f, sizeof pre); memset(suf, -0x3f, sizeof suf);
        B = sqrt(n); tot = (n - 1) / B + 1;
        for (int i = 1; i <= tot; i++) L[i] = R[i - 1] + 1, R[i] = B * i; R[tot] = n;
        for (int i = 1; i <= tot; i++) {
            for (int j = L[i]; j <= R[i]; j++) {
                bel[j] = i;
                int now = 0, x = a[j];
                for (int k = L[i]; k <= R[i]; k++) now += o(k, x), pre[i][x] = max(pre[i][x], now);
                sum[i][x] = now; now = 0;
                for (int k = R[i]; k >= L[i]; k--) now += o(k, x), suf[i][x] = max(suf[i][x], now);
            }
            for (int x = len; x >= 1; x--) {
                sum[i][x] = max(sum[i][x], sum[i][x + 1]);
                pre[i][x] = max(pre[i][x], pre[i][x + 1]);
                suf[i][x] = max(suf[i][x], suf[i][x + 1]);
//              cout << sum[i][x] << ' ' << pre[i][x] << ' ' << suf[i][x] << '\n';
            }
        }
    }
    int getsum(int l, int r, int x) {
        int p = bel[l], q = bel[r], now = 0;
        if (p == q) {
            for (int i = l; i <= r; i++) now += o(i, x);
            return now;
        }
        for (int i = l; i <= R[p]; i++) now += o(i, x);
        for (int i = p + 1; i <= q - 1; i++) now += sum[i][x];
        for (int i = L[q]; i <= r; i++) now += o(i, x);
        return now;
    }
    int getpre(int l, int r, int x) {
        int p = bel[l], q = bel[r], now = 0, mx = 0;
        if (p == q) {
            for (int i = l; i <= r; i++) now += o(i, x), mx = max(mx, now);
            return mx;
        }
        for (int i = l; i <= R[p]; i++) now += o(i, x), mx = max(mx, now);
        for (int i = p + 1; i <= q - 1; i++) mx = max(mx, now + pre[i][x]), now += sum[i][x];
        for (int i = L[q]; i <= r; i++) now += o(i, x), mx = max(mx, now);
        return mx;
    }
    int getsuf(int l, int r, int x) {
        int p = bel[l], q = bel[r], now = 0, mx = 0;
        if (p == q) {
            for (int i = r; i >= l; i--) now += o(i, x), mx = max(mx, now);
            return mx;
        }
        for (int i = r; i >= L[q]; i--) now += o(i, x), mx = max(mx, now);
        for (int i = q - 1; i >= p + 1; i--) mx = max(mx, now + suf[i][x]), now += sum[i][x];
        for (int i = R[p]; i >= l; i--) now += o(i, x), mx = max(mx, now);
        return mx;
    }
} using namespace ArrayDiv;

bool check(int x) { return getsuf(q[1], q[2], x) + getsum(q[2] + 1, q[3] - 1, x) + getpre(q[3], q[4], x) >= 0; }

int main() {
//  ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
    sort(b + 1, b + n + 1); len = unique(b + 1, b + n + 1) - (b + 1);
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
    init();
    for (cin >> Q; Q--; ) {
        for (int i = 1; i <= 4; i++) cin >> q[i], q[i] = (q[i] + lst) % n + 1;
        sort(q + 1, q + 4 + 1);
        int l = 1, r = len;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        cout << (lst = b[l]) << '\n';
    }
    return 0;
}

/*
5
2 3 9 1 1 
1
3 2 2 2
*/