P2839 [国家集训队]middle 题解

· · 题解

AC 的第一道紫题，以此留念。

Sol

若直接上手求最大中位数，会发现中位数不仅受相对大小影响，还会受数量的影响，因此难以处理。

因此考虑二分答案。

我们设二分出的中位数为 mid，问题就转化为是否存在一个满足条件的区间，其中位数 mid' ≥ mid。

因为 mid 是确定的，可直接统计大于 mid 和小于 mid 数的数量 n_1,n_2。若 n_1 ≥ n_2，则 mid 可以取到。

考虑最大化 n_1，最小化 n_2。设大于 mid 的数为 1，小于 mid 的数为 -1，在 [a,b] 中找一个最大后缀，[c,d] 中找一个最大前缀并判断即可。

发现区间最大前缀、后缀与区间和均可用线段树维护，但问题是因为要求关于所有 mid 对应的所有数的相对大小，因此要开 n 棵，会爆时限空限。

考虑将原数组排序，会发现当第 i 个元素作中位数和第 i + 1 个元素作中位数时，只会对应线段树中一个节点的值由 1 变为 -1，用可持久化线段树维护即可。

时间复杂度 O(n\log^2n)。实现时细节颇多。

代码

#include<iostream>
#include<algorithm>

using namespace std;
#define ll long long

const int MAXN = 2e4 + 10;
struct item
{
    ll num, val;
}a[MAXN];
struct segmentTree
{
    ll ls, rs, lm, rm, sum;
}tree[MAXN << 6];
ll lsh[MAXN], pos[MAXN], t[MAXN], root[MAXN], q[4];
ll n, Q, ans;

bool cmp(item x, item y) { return x.val < y.val; }

ll cnt;
void push_up(ll x)
{
    tree[x].sum = tree[tree[x].ls].sum + tree[tree[x].rs].sum;
    tree[x].lm = max(tree[tree[x].ls].lm, tree[tree[x].ls].sum + tree[tree[x].rs].lm);
    tree[x].rm = max(tree[tree[x].rs].rm, tree[tree[x].rs].sum + tree[tree[x].ls].rm);
}
void build(ll &x, ll l, ll r)
{
    x = ++cnt;
    if (l == r)
    {
        tree[x].sum = 1, tree[x].lm = 1, tree[x].rm = 1;
        return;
    }
    ll mid = (l + r) >> 1;
    build(tree[x].ls, l, mid);
    build(tree[x].rs, mid + 1, r);
    push_up(x);
}
void change(ll &now, ll last, ll l, ll r, ll p)
{
    now = ++cnt;
    if (l == r)
    {
        tree[now].sum = -1, tree[now].lm = -1, tree[now].rm = -1;
        return;
    }
    tree[now].ls = tree[last].ls; 
    tree[now].rs = tree[last].rs;
    ll mid = (l + r) >> 1;
    if (p <= mid) change(tree[now].ls, tree[last].ls, l, mid, p);
    else change(tree[now].rs, tree[last].rs, mid + 1, r, p);
    push_up(now);
}

ll query_sum(ll x, ll l, ll r, ll L, ll R)
{
    if (L <= l && R >= r) 
        return tree[x].sum;
    else if (L <= r && R >= l)
    {
        ll mid = (l + r) >> 1;
        return query_sum(tree[x].ls, l, mid, L, R) + query_sum(tree[x].rs, mid + 1, r, L, R);
    }
    else return 0;
}
ll query_lmax(ll x, ll l, ll r, ll L, ll R)
{
    if (L <= l && R >= r)
        return tree[x].lm;
    else if (L <= r && R >= l)
    {
        ll mid = (l + r) >> 1;
        return max(query_lmax(tree[x].ls, l, mid, L, R), 
                    query_sum(tree[x].ls, l, mid, L, R) + query_lmax(tree[x].rs, mid + 1, r, L, R));
    }
    else return 0;
}
ll query_rmax(ll x, ll l, ll r, ll L, ll R)
{
    if (L <= l && R >= r)
        return tree[x].rm;
    else if (L <= r && R >= l)
    {
        ll mid = (l + r) >> 1;
        return max(query_rmax(tree[x].rs, mid + 1, r, L, R), 
                    query_sum(tree[x].rs, mid + 1, r, L, R) + query_rmax(tree[x].ls, l, mid, L, R));
    }
    else return 0;
}

ll res;
void my_unique()
{
    res = 0;
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++)
        if (a[i].val == a[i - 1].val && i > 1)
            lsh[a[i].num] = res;
        else
            lsh[a[i].num] = ++res, pos[res] = i, t[res] = a[i].val; 
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].val, a[i].num = i;

    my_unique();
    build(root[1], 1, n);
    for (int i = 2; i <= n; i++) 
        change(root[i], root[i - 1], 1, n, a[i - 1].num);

    cin >> Q;
    while (Q--)
    {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        q[0] = (a + ans) % n + 1; q[1] = (b + ans) % n + 1;
        q[2] = (c + ans) % n + 1; q[3] = (d + ans) % n + 1;
        sort(q, q + 4);
        ll l = 1, r = res;
        while (l <= r)
        {
            ll mid = (l + r) >> 1;
            ll tot1 = query_sum(root[pos[mid]], 1, n, q[1], q[2]);
            ll tot2 = query_rmax(root[pos[mid]], 1, n, q[0], q[1] - 1);
            ll tot3 = query_lmax(root[pos[mid]], 1, n, q[2] + 1, q[3]);
            if (tot1 + tot2 + tot3 >= 0)
                l = mid + 1, ans = t[mid];
            else
                r = mid - 1;
        }
        cout << ans << endl;
    }
    return 0;   
}