DDOSvoid's Blog

Luogu P2839 [国家集训队]middle

发表于 分类于
本文字数： 2.8k 阅读时长 ≈ 3 分钟

题目描述

https://www.luogu.com.cn/problem/P2839

简要题意：给定一个长度为 $n$​ 的序列 $a$​ 和 $m$​ 次询问，每次询问给定两个区间 $[l_1,r_1],[l_2,r_2]$​，保证 $r_1<l_2$​，求左端点在 $[l_1,r_1]$​，右端点在 $[l_2,r_2]$​ 的所有区间中，中位数最大的区间，询问强制在线

$n\le 20000,m\le 25000$

Solution

对于中位数，我们考虑二分 $x$，然后令大于等于 $x$ 的数为 $1$，小于 $x$ 的数为 $-1$，那么如果区间和大于等于 $0$，则表示中位数大于等于 $x$

注意到区间不相交，那么我们二分之后，肯定选择 $[l_1,r_1]$ 的后缀最大值加 $[r_1+1,l_2-1]$ 的和加 $[l_2,r_2]$ 的前缀最大值

那么现在的问题是如何维护这些东西，注意到随着二分 $x$ 的值的变化，越来越多的 $1$ 会变成 $-1$，且一共只会变化 $O(n)$​，且启示我们用主席树来维护这个东西

时间复杂度 $O(n\log ^2 n)$​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <algorithm>
#include <vector>
#define maxn 20010
#define INF 1000000000
using namespace std;

int n, m, a[maxn];

int b[maxn], cnt;
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = a[i];
    sort(b + 1, b + n + 1); cnt = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
}

#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct Zhuxi {
    int v, pre, suf, ch[2];
} T[maxn * 25]; int rt[maxn], top;
inline Zhuxi maintain(const Zhuxi &ls, const Zhuxi &rs, int lson = 0, int rson = 0) {
    Zhuxi o; o.ch[0] = lson; o.ch[1] = rson;
    o.v = ls.v + rs.v;
    o.pre = max(ls.pre, ls.v + rs.pre);
    o.suf = max(rs.suf, rs.v + ls.suf);
    return o;
}

void build(int &i, int l, int r) {
    i = ++top; int m = l + r >> 1;
    if (l == r) return T[i] = { 1, 1, 1, 0, 0 }, void();
    build(lc, l, m); build(rc, m + 1, r);
    T[i] = maintain(T[lc], T[rc], lc, rc);
}

void update(int &i, int j, int l, int r, int k, int v) {
    i = ++top; T[i] = T[j]; int m = l + r >> 1; 
    if (l == r) return T[i] = { v, v, v }, void();
    if (k <= m) update(lc, Lc, l, m, k, v);
    else update(rc, Rc, m + 1, r, k, v);
    T[i] = maintain(T[lc], T[rc], lc, rc);
}

Zhuxi query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return { 0, -INF, -INF };
    if (L <= l && r <= R) return T[i];
    int m = l + r >> 1;
    return maintain(query(lc, l, m, L, R), query(rc, m + 1, r, L, R));
}

void change(int &a, int &b, int &c, int &d) {
    int tmp[4] = { a, b, c, d };
    sort(tmp, tmp + 4);
    a = tmp[0]; b = tmp[1]; c = tmp[2]; d = tmp[3];
}

vector<int> A[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; build(rt[0], 1, n); 
    for (int i = 1; i <= n; ++i) cin >> a[i]; init_hash();
    for (int i = 1; i <= n; ++i) A[a[i]].push_back(i);
    for (int i = 1; i <= cnt; ++i) {
        rt[i] = rt[i - 1];
        for (auto t : A[i]) update(rt[i], rt[i], 1, n, t, -1);
    } 
    cin >> m; int lans = 0; 
    for (int i = 1; i <= m; ++i) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        a = (a + lans) % n + 1; b = (b + lans) % n + 1;
        c = (c + lans) % n + 1; d = (d + lans) % n + 1;
        change(a, b, c, d);

        int l = 1, r = cnt, mid, ans;
        while (l <= r) {
            mid = l + r >> 1;
            Zhuxi t1 = query(rt[mid - 1], 1, n, a, b), t2 = query(rt[mid - 1], 1, n, b + 1, c - 1),
                t3 = query(rt[mid - 1], 1, n, c, d);
            if (t1.suf + t2.v + t3.pre >= 0) ans = mid, l = mid + 1;
            else r = mid - 1;
        } cout << (lans = ::b[ans]) << "\n";
    }
    return 0;
}