CSES Range Queries - Star's Blog

这些是寒假集训新做的题，之前做过的不会再专门写一遍题解了，如果需要代码可以看仓库。

Visible Buildings Queries#

单调栈维护每个元素右侧第一个比他大的元素的位置，然后用倍增查询。

1
#include <iostream>
2
#include <stack>
3

4
using namespace std;
5

6
const int N = 100010;
7

8
stack<int> st;
9
int a[N], f[N][17];
10

11
int main() {
12
    ios::sync_with_stdio(0);
13
    cin.tie(0), cout.tie(0);
14
    int n, q;
15
    cin >> n >> q;
16
    for (int i = 1; i <= n; ++i) {
17
        cin >> a[i];
18
        while (!st.empty() && a[i] > a[st.top()]) {
19
            f[st.top()][0] = i;
20
            st.pop();
21
        }
22
        st.emplace(i);
23
    }
24
    while (!st.empty()) {
25
        f[st.top()][0] = n + 1;
26
        st.pop();
27
    }
28
    f[n + 1][0] = n + 1;
29
    for (int j = 1; j < 17; ++j) {
30
        for (int i = 1; i <= n + 1; ++i) {
31
            f[i][j] = f[f[i][j - 1]][j - 1];
32
        }
33
    }
34
    while (q--) {
35
        int l, r, res = 0;
36
        cin >> l >> r;
37
        for (int i = 16; i >= 0; --i) {
38
            if (f[l][i] <= r) {
39
                l = f[l][i];
40
                res += 1 << i;
41
            }
42
        }
43
        cout << res + 1 << endl;
44
    }
45
    return 0;
46
}

Range Interval Queries#

主席树（可持久化线段树）板子，离散化之后维护一个可持久化的权值线段树查询的时候用两颗不同版本的树作差。

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
using namespace std;
6

7
const int N = 200010;
8

9
struct Node {
10
    int val, ls, rs;
11
} tr[N * 20];
12
int tot;
13

14
vector<int> values;
15
int a[N], rt[N];
16

17
void pushup(int u) {
18
    tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
19
}
20

21
void modify(int &u, int v, int l, int r, int p, int val) {
22
    u = ++tot;
23
    tr[u] = tr[v];
24
    if (l == r) tr[u].val += val;
25
    else {
26
        int mid = l + r >> 1;
27
        if (p <= mid) modify(tr[u].ls, tr[v].ls, l, mid, p, val);
28
        else modify(tr[u].rs, tr[v].rs, mid + 1, r, p, val);
29
        pushup(u);
30
    }
31
}
32

33
int query(int u, int v, int l, int r, int ql, int qr) {
34
    if (u == 0 && v == 0) return 0;
35
    if (ql <= l && r <= qr) return tr[v].val - tr[u].val;
36
    else {
37
        int mid = l + r >> 1;
38
        int res = 0;
39
        if (ql <= mid) res = query(tr[u].ls, tr[v].ls, l, mid, ql, qr);
40
        if (qr > mid) res += query(tr[u].rs, tr[v].rs, mid + 1, r, ql, qr);
41
        return res;
42
    }
43
}
44

45
int main() {
46
    ios::sync_with_stdio(0);
47
    cin.tie(0), cout.tie(0);
48
    int n, q;
49
    cin >> n >> q;
50
    for (int i = 1; i <= n; ++i) {
51
        cin >> a[i];
52
        values.emplace_back(a[i]);
53
    }
54
    sort(values.begin(), values.end());
55
    values.erase(unique(values.begin(), values.end()), values.end());
56
    for (int i = 1; i <= n; ++i) {
57
        modify(rt[i], rt[i - 1], 1, n, lower_bound(values.begin(), values.end(), a[i]) - values.begin() + 1, 1);
58
    }
59
    while (q--) {
60
        int a, b, c, d;
61
        cin >> a >> b >> c >> d;
62
        c = lower_bound(values.begin(), values.end(), c) - values.begin() + 1;
63
        d = upper_bound(values.begin(), values.end(), d) - values.begin();
64
        cout << query(rt[a - 1], rt[b], 1, n, c, d) << endl;
65
    }
66
    return 0;
67
}

Subarray Sum Queries II#

最大子段和，上一道是带修改的，这一道是静态查询。都是线段树维护和，最大前缀和，最大后缀和，最大子段和。推荐开结构体，建议专门写一个 merge 函数合并两个节点。

1
#include <cstdio>
2
#include <iostream>
3

4
using namespace std;
5

6
const int N = 200010;
7

8
struct Node {
9
    long long s, ls, rs, ms;
10
} tr[N << 2];
11

12
Node merge(Node a, Node b) {
13
    Node res;
14
    res.s = a.s + b.s;
15
    res.ls = max(a.ls , a.s + b.ls);
16
    res.rs = max(b.rs, a.rs + b.s);
17
    res.ms = max(a.rs + b.ls, max(a.ms, b.ms));
18
    return res;
19
}
20

21
void modify(int u, int l, int r, int p, int v) {
22
    if (l == r) {
23
        tr[u].s = v;
24
        tr[u].ls = tr[u].rs = tr[u].ms = max(0, v);
25
        return;
26
    }
27
    int mid = l + r >> 1;
28
    if (p <= mid) modify(u << 1, l, mid, p, v);
29
    else modify(u << 1 | 1, mid + 1, r, p, v);
30
    tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
31
}
32

33
Node query(int u, int l, int r, int ql, int qr) {
34
    if (ql <= l && r <= qr) return tr[u];
35
    int mid = l + r >> 1;
36
    Node res = {0, 0, 0, 0};
37
    if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
38
    if (qr > mid) res = merge(res, query(u << 1 | 1, mid + 1, r, ql, qr));
39
    return res;
40
}
41

42
int main() {
43
    int n, q;
44
    scanf("%d%d", &n, &q);
45
    for (int i = 1; i <= n; ++i) {
46
        int t;
47
        scanf("%d", &t);
48
        modify(1, 1, n, i, t);
49
    }
50
    while (q--) {
51
        int l, r;
52
        scanf("%d%d", &l, &r);
53
        printf("%lld\n", query(1, 1, n, l, r).ms);
54
    }
55
    return 0;
56
}

Distinct Values Queries II#

把所有可能的权值离散化，各开一个 set 存所有的出现位置。开线段树维护区间内的元素前一次出现位置的最大值。

对于一个修改操作
- 找到旧权值的 set，删掉旧的那一次出现的下标，修改线段树，把后一次的下标的权值改成前一次的下标
- 把下标插入到新权值的 set，修改线段树，当前下标的值改成前一次出现的权值，后一次出现的下标的值改成当前下标
对于一个查询操作
- 只需要查区间最大值是否大于左端点即可

1
#include <cstdio>
2
#include <iostream>
3

4
using namespace std;
5

6
const int N = 200010;
7

8
struct Node {
9
    long long s, ls, rs, ms;
10
} tr[N << 2];
11

12
Node merge(Node a, Node b) {
13
    Node res;
14
    res.s = a.s + b.s;
15
    res.ls = max(a.ls , a.s + b.ls);
16
    res.rs = max(b.rs, a.rs + b.s);
17
    res.ms = max(a.rs + b.ls, max(a.ms, b.ms));
18
    return res;
19
}
20

21
void modify(int u, int l, int r, int p, int v) {
22
    if (l == r) {
23
        tr[u].s = v;
24
        tr[u].ls = tr[u].rs = tr[u].ms = max(0, v);
25
        return;
26
    }
27
    int mid = l + r >> 1;
28
    if (p <= mid) modify(u << 1, l, mid, p, v);
29
    else modify(u << 1 | 1, mid + 1, r, p, v);
30
    tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
31
}
32

33
Node query(int u, int l, int r, int ql, int qr) {
34
    if (ql <= l && r <= qr) return tr[u];
35
    int mid = l + r >> 1;
36
    Node res = {0, 0, 0, 0};
37
    if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
38
    if (qr > mid) res = merge(res, query(u << 1 | 1, mid + 1, r, ql, qr));
39
    return res;
40
}
41

42
int main() {
43
    int n, q;
44
    scanf("%d%d", &n, &q);
45
    for (int i = 1; i <= n; ++i) {
46
        int t;
47
        scanf("%d", &t);
48
        modify(1, 1, n, i, t);
49
    }
50
    while (q--) {
51
        int l, r;
52
        scanf("%d%d", &l, &r);
53
        printf("%lld\n", query(1, 1, n, l, r).ms);
54
    }
55
    return 0;
56
}

Movie Festival Queries#

NOTE
这道题看了题解

思路比较巧妙，开一个数组，对于每一场 movie 在左端点的下标的位置存右端点的位置，做一个后缀 min 能得到从某个时间开始看电影看完一场的最早时间，然后用倍增就解决了。

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <cstring>
5

6
using namespace std;
7

8
const int N = 1000010;
9
int f[N][20];
10

11
int main() {
12
    ios::sync_with_stdio(0);
13
    cin.tie(0), cout.tie(0);
14
    int n, q, m = 1000000;
15
    cin >> n >> q;
16
    for (int i = 1; i <= m + 1; ++i) {
17
        f[i][0] = m + 1;
18
    }
19
    for (int i = 1; i <= n; ++i) {
20
        int l, r;
21
        cin >> l >> r;
22
        f[l][0] = min(f[l][0], r);
23
    }
24
    for (int i = m; i; --i) {
25
        f[i][0] = min(f[i][0], f[i + 1][0]);
26
    }
27
    for (int j = 1; j < 20; ++j) {
28
        for (int i = 1; i <= m + 1; ++i) {
29
            f[i][j] = f[f[i][j - 1]][j - 1];
30
        }
31
    }
32
    while (q--) {
33
        int l, r, res = 0;
34
        cin >> l >> r;
35
        for (int i = 19; i >= 0; --i) {
36
            if (f[l][i] <= r) {
37
                l = f[l][i];
38
                res |= 1 << i;
39
            }
40
        }
41
        cout << res << endl;
42
    }
43
    return 0;
44
}

Range Queries and Copies#

刚开始我以为他是一个数组一直往尾部加，又看了看发现他是新建一整组，所以又是一个主席树。

操作 1：单点修改。
操作 2：找到 array k 的主席树的根的下标，从这个根开始做区间查询。
操作 3：直接往存根的数组里加一项，复制 array k 的根的下标。

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
using namespace std;
6

7
typedef long long LL;
8
const int N = 200010;
9

10
struct Node {
11
    LL val;
12
    int ls, rs;
13
} tr[N * 24];
14
int tot;
15

16
int a[N], rt[N], cnt = 1;
17

18
void pushup(int u) {
19
    tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
20
}
21

22
void build(int &u, int l, int r) {
23
    u = ++tot;
24
    if (l == r) tr[u] = {a[l]};
25
    else {
26
        int mid = l + r >> 1;
27
        build(tr[u].ls, l, mid), build(tr[u].rs, mid + 1, r);
28
        pushup(u);
29
    }
30
}
31

32
void modify(int &u, int v, int l, int r, int p, int val) {
33
    u = ++tot;
34
    tr[u] = tr[v];
35
    if (l == r) tr[u].val = val;
36
    else {
37
        int mid = l + r >> 1;
38
        if (p <= mid) modify(tr[u].ls, tr[v].ls, l, mid, p, val);
39
        else modify(tr[u].rs, tr[v].rs, mid + 1, r, p, val);
40
        pushup(u);
41
    }
42
}
43

44
LL query(int u, int l, int r, int ql, int qr) {
45
    if (u == 0) return 0;
46
    if (ql <= l && r <= qr) return tr[u].val;
47
    else {
48
        int mid = l + r >> 1;
49
        LL res = 0;
50
        if (ql <= mid) res = query(tr[u].ls, l, mid, ql, qr);
51
        if (qr > mid) res += query(tr[u].rs, mid + 1, r, ql, qr);
52
        return res;
53
    }
54
}
55

56
int main() {
57
    ios::sync_with_stdio(0);
58
    cin.tie(0), cout.tie(0);
59
    int n, q;
60
    cin >> n >> q;
61
    for (int i = 1; i <= n; ++i) {
62
        cin >> a[i];
63
    }
64
    build(rt[cnt], 1, n);
65
    while (q--) {
66
        int op;
67
        cin >> op;
68
        if (op == 1) {
69
            int a, k, x;
70
            cin >> k >> a >> x;
71
            modify(rt[k], rt[k], 1, n, a, x);
72
        }
73
        else if (op == 2) {
74
            int k, a, b;
75
            cin >> k >> a >> b;
76
            cout << query(rt[k], 1, n, a, b) << endl;
77
        }
78
        else {
79
            int k;
80
            cin >> k;
81
            rt[++cnt] = rt[k];
82
        }
83
    }
84
    return 0;
85
}

Missing Coin Sum Queries#

NOTE
事实证明不能做太多的数据结构，我该休息了。被一个 int 爆了一个小时才发现，还有这么蠢的人吗😭

先回顾单独的 Missing Coin Sum 怎么做，如果一组硬币已经可以表示 $\left[1, m\right]$ ，那么加入一个面值为 $a_i$ 的硬币，当且仅当 $a_i \le m$ 的时候才能保证 $\left[1, m + a_i\right]$ 的值都能表示，否则中间一定有间断，第一个不能表示的还是 $m + 1$ 。从小往大推，不断这样扩大区间直到不能扩大就可以得到答案。

初始化答案 $res = 1$ ；
尝试把所有小于答案的数相加得到 $s$ $s$
- 如果 $s \ge res$ ，更新答案 $res = s + 1$ ，转到 2 继续尝试更大的能不能表示。
- 否则 $res$ 就是答案。

那么继续来考虑现在的问题，不难发现上面的流程中 $res$ 是指数级增长的，只要能快速算出这个小于等于 $res$ 的数的和就能不 TLE。这个可以用离散化 + 主席树实现。

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
using namespace std;
6

7
typedef long long LL;
8
const int N = 200010;
9

10
struct Node {
11
    LL val;
12
    int ls, rs;
13
} tr[N * 20];
14
int tot;
15

16
vector<LL> values;
17
int a[N], rt[N];
18

19
void pushup(int u) {
20
    tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
21
}
22

23
void modify(int &u, int v, int l, int r, int p, int val) {
24
    u = ++tot;
25
    tr[u] = tr[v];
26
    if (l == r) tr[u].val += val;
27
    else {
28
        int mid = l + r >> 1;
29
        if (p <= mid) modify(tr[u].ls, tr[v].ls, l, mid, p, val);
30
        else modify(tr[u].rs, tr[v].rs, mid + 1, r, p, val);
31
        pushup(u);
32
    }
33
}
34

35
LL query(int u, int v, int l, int r, int ql, int qr) {
36
    if (ql > qr) return 0;
37
    if (u == 0 && v == 0) return 0;
38
    if (ql <= l && r <= qr) return tr[v].val - tr[u].val;
39
    else {
40
        int mid = l + r >> 1;
41
        LL res = 0;
42
        if (ql <= mid) res = query(tr[u].ls, tr[v].ls, l, mid, ql, qr);
43
        if (qr > mid) res += query(tr[u].rs, tr[v].rs, mid + 1, r, ql, qr);
44
        return res;
45
    }
46
}
47

48
int main() {
49
    ios::sync_with_stdio(0);
50
    cin.tie(0), cout.tie(0);
51
    int n, q;
52
    cin >> n >> q;
53
    for (int i = 1; i <= n; ++i) {
54
        cin >> a[i];
55
        values.emplace_back(a[i]);
56
    }
57
    sort(values.begin(), values.end());
58
    values.erase(unique(values.begin(), values.end()), values.end());
59
    int m = values.size();
60
    for (int i = 1; i <= n; ++i) {
61
        modify(rt[i], rt[i - 1], 1, m, lower_bound(values.begin(), values.end(), a[i]) - values.begin() + 1, a[i]);
62
    }
63
    while (q--) {
64
        int l, r;
65
        cin >> l >> r;
66
        LL res = 1;
67
        int T = 100;
68
        while (T--) {
69
            /*
70
            if Q is valid:
71
                \sum [1, Q] is valid
72
            */
73
            LL s = query(rt[l - 1], rt[r], 1, m, 1, upper_bound(values.begin(), values.end(), res) - values.begin());
74
            if (res == s + 1) break;
75
            else res = s + 1;
76
        }
77
        cout << res << endl;
78
    }
79
    return 0;
80
}