主席树 WA30 求调

RT，一直 WA 30 也不知道为什么……

#include <algorithm>
#include <cstdio>
#include <vector>
#define inf 100000000

using namespace std;

int cnt, rt[20002];
struct node{
    int l, r, pmax, smax, sum;
}tr[20000001];
inline void pushup(int u){
    tr[u].pmax = max(tr[tr[u].l].pmax, tr[tr[u].l].sum + tr[tr[u].r].pmax);
    tr[u].smax = max(tr[tr[u].r].smax, tr[tr[u].l].smax + tr[tr[u].r].sum);
    tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}
void update(int u1, int& u2, int l, int r, int p, int x){
    if (!u2) u2 = ++ cnt;
    if (l == r){
        tr[u2].pmax = tr[u2].smax = tr[u2].sum = x;
        return;
    }
    int mid = l + r >> 1;
    if (p <= mid) tr[u2].r = tr[u1].r, update(tr[u1].l, tr[u2].l, l, mid, p, x);
    else tr[u2].l = tr[u1].l, update(tr[u1].r, tr[u2].r, mid + 1, r, p, x);
    pushup(u2);
}
node query(int u, int l, int r, int L, int R){
    if (R < l || r < L) return {0, 0, -inf, -inf, 0};
    if (L <= l && r <= R) return tr[u];
    int mid = l + r >> 1;
    node a = query(tr[u].l, l, mid, L, R), b = query(tr[u].r, mid + 1, r, L, R);
    return {0, 0, max(a.pmax, a.sum + b.pmax), max(b.smax, a.smax + b.sum), a.sum + b.sum};
}

int n, q, a[20002], _, b[20002], t[4], ll, lr, rl, rr, ans;
vector<int> p[20002];
void build(int &u, int l, int r){
    u = ++ cnt;
    if (l == r){
        tr[u] = {0, 0, -1, -1, -1};
        return;
    }
    int mid = l + r >> 1;
    build(tr[u].l, l, mid);
    build(tr[u].r, mid + 1, r);
    pushup(u);
}
bool check(int x){
    int tmp = 0;
    if (lr + 1 <= rl - 1) tmp = query(rt[x], 1, n, lr + 1, rl - 1).sum;
    int A = query(rt[x], 1, n, ll, lr).smax, B = query(rt[x], 1, n, rl, rr).pmax;
    return A + tmp + B >= 0;
}
int main(){
    scanf("%d", &n);
    for (int i = 1;i <= n;i ++) scanf("%d", &a[i]), b[++ _] = a[i];
    sort(b + 1, b + _ + 1);
    _ = unique(b + 1, b + _ + 1) - b - 1;
    for (int i = 1;i <= n;i ++) a[i] = lower_bound(b + 1, b + _ + 1, a[i]) - b;
    for (int i = 1;i <= n;i ++) p[a[i]].push_back(i);
    build(rt[_ + 1], 1, n);
    for (int i = _;i >= 1;i --){
        for (int j = 0;j < p[i].size();j ++){
            update(rt[i + 1], rt[i], 1, n, p[i][j], 1);
        }
    }
    scanf("%d", &q);
    while (q --){
        scanf("%d%d%d%d", &ll, &lr, &rl, &rr);
        t[0] = (ll + ans) % n + 1, t[1] = (lr + ans) % n + 1, t[2] = (rl + ans) % n + 1, t[3] = (rr + ans) % n + 1;
        sort(t, t + 4);
        ll = t[0], lr = t[1], rl = t[2], rr = t[3];
        int l = 1, r = _ + 1;
        while (r - l > 1){
            int mid = l + r >> 1;
            if (check(mid)) l = mid;
            else r = mid;
        }
        printf("%d\n", ans = b[l]);
    }
}