安吉D3-T2 - Jerry's blog

原题呈现

题目描述#

巴蜀地区的地势非常崎岖，山峰耸立．我们将每座山峰依次编号为 $1$ 到 $n$ ，第 $i$ 座山峰的高度为 $h_i$ ．

总共 $m$ 支施工队，每支施工队的能力各不相同——有些擅长高空作业，有些擅长隧道构建．每支施工队有两个参数：

$a_i$ ：最高能施工的高度（即可以处理不超过该高度的山峰）；
$b_i$ ：最长能修建的隧道长度（即最多可以连续炸掉 $b_i - 1$ 座山来修建隧道，因为出口和入口需要额外加固）．

施工队需要从起点 $1$ 出发，修建一条直达 $n$ 的道路．我们规定 $1$ 号和 $n$ 号都是平地（高度为 $0$ ）．

施工队可以从任意一个不超过最高施工高度的高度开始，修建一条高架和隧道结合的道路．一旦确定了道路的初始高度，整条道路的高度就不能再有任何变化．因此：

如果某座山峰的高度低于或等于施工高度，则只需正常修建高架即可；
如果某座山峰的高度高于施工高度，则必须炸山修隧道（即施工队需要在这座山上打通隧道）．

请判断每支施工队是否能够胜任这项工作．

输入格式#

第一行包含两个空格分隔的整数 $n$ 和 $m$ ．第二行包含 $n$ 个空格分隔的整数，其中第 $i$ 个为 $h_i$ （第 $i$ 座山峰的高度）．接下来 $m$ 行，每行包含两个空格分隔的整数 $a_i$ 和 $b_i$ ，代表第 $i$ 支施工队的最大施工高度和最长隧道长度．

输出格式#

输出共 $m$ 行．第 $i$ 行输出一个整数：如果第 $i$ 支施工队能够胜任工作，则为 1，否则为 0．

样例#

输入 #1#

1
8 7
2
0 3 8 5 6 9 0 0
3
0 5
4
0 6
5
6 2
6
8 1
7
10 1
8
5 3
9
150 7

输出 #1#

数据范围#

数据点	分值	限制
1	40 pts	$0 \le n, m \le 5000$ ， $1 \le h_i, a_i \le 10^6$
2	10 pts	额外满足 $a_i \le a_{i+1}$ 且 $b_i \le b_{i+1}$
3	100 pts	$0 \le n, m \le 10^5$ ， $1 \le h_i, a_i \le 10^9$ ， $1 \le b_i \le n-1$

题意可以理解为：求一段序列中一段最大的连续区间 $s$ ，满足： $s$ 内每一个数都大于 $a_i$ ，求 $s$ 的大小 $l_s$ ，将其和 $b_i$ 比大小，且多测．

考虑到每个施工队施工的高度越高，障碍越少，且消失的障碍不会回复，因而所需要的 $b_i$ 也越少．

用一个更加形象的例子，现在有 $n$ 道题， $m$ 个学生，每个学生有一个能力值 $a_i$ ，有一个耐力值 $b_1$ ，每道题有一个难度 $h_j$ ，现在，让每一名学生来做这些题目，若 $\exists j$ 使得 $a_i < h_j$ ，则这名学生做不出来第 $j$ 道题，若有连续 $b_i-1$ 道题这位学生都做不出来，这位学生就会崩溃，求这位学生会不会崩溃．

显然，如果学生 $s_1$ 做不出来题目 $i$ ，那么能力弱于 $s_1$ 的 $s_2$ 也肯定做不出来题目 $i$ ．

因此使用离线处理．将每一次询问（即每一个施工队）按 $a_i$ 从高到低排序，将每一座山也按照高度从高到低排序．模拟一个收容山的并查集，用于记录已经对当前施工队产生影响的障碍，一开始，并查集为空，设未加入并查集且最高的山是第 $m$ 座，高度为 $h_m$ ，则对于每一次询问：

检查 $a_i$ $a_{i}$ 和 $h_m$ $h_{m}$ 的大小关系
- 若当前询问的 $a_i$ 比 $h_m$ 大或等于（即第 $m$ 座山，也就是未记录的最高的山都无法对该施工队增加障碍），跳过这个阶段．
- 否则，说明第 $m$ 座山成为该施工队施工的新的障碍（由于施工队按照 $a_i$ 从高到低排列，对靠前者造成影响的山，也会对靠后者造成影响），将 $m$ 加入并查集，且与第 $m-1$ 座和第 $m+1$ 座（如果已经加入并查集的话）合并，并维护每个集合的左边界 $l$ 和右边界 $r$ ，统计最大的区间 $max$ （初始由于没有山加入到并查集，所以是 0）．重复这个操作，直到当前询问的 $a_i$ 比 $h_m$ 大或等于．
将 $ans[i]$ 设置为 $max$ ．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N = 1e5 + 100;
4
int n, m, maxb, ans[N];
5

6
struct Mout {
7
    int h, id;
8
    friend bool operator<(const Mout a, const Mout b) { return a.h > b.h; }
9
};
10

11
struct Team {
12
    int h, b, id;
13
    friend bool operator<(const Team a, const Team b) { return a.h > b.h; }
14
};
15

16
struct Node {
17
    int fa, l, r;
18
} d[N];
19

20
// 并查集
21
struct DSU {
22
    Node *d;
23
    DSU(Node *d) : d(d) {};
24
    // 将节点 x 加入到并查集之中
25
    void active(int x) {
26
        d[x].fa = x;
27
        d[x].l = x, d[x].r = x;
28
        maxb = max(maxb, 1);
29
    }
30
    int find(int x) {
31
        if (d[x].fa == x)
32
            return x;
33
        d[x].fa = find(d[x].fa);
34
        return d[x].fa;
35
    }
36
    void merge(int a, int b) {
37
        a = find(a), b = find(b);
38
        if (a == b)
39
            return;
40
        d[a].fa = b;
41
        d[b].l = min(d[b].l, d[a].l);
42
        d[b].r = max(d[b].r, d[a].r);
43
        maxb = max(maxb, d[b].r - d[b].l + 1);
44
    }
45
} dsu(d);
46

47
Mout h[N];
48
Team a[N];
49
int main() {
50
    freopen("mountain.in", "r", stdin);
51
    freopen("mountain.out", "w", stdout);
52
    cin >> n >> m;
53
    for (int i = 1; i <= n; i++) {
54
        cin >> h[i].h;
55
        h[i].id = i;
56
    }
57
    for (int i = 1; i <= m; i++) {
58
        cin >> a[i].h >> a[i].b;
59
        a[i].id = i;
60
    }
61
    sort(h + 1, h + n + 1);
62
    sort(a + 1, a + m + 1);
63
    int ptr = 0;
64
    for (int i = 1; i <= m; i++) {
65
        int reqH = a[i].h;
66
        while (h[ptr + 1].h > reqH) {
67
            ptr++;
68
            int curId = h[ptr].id;
69
            dsu.active(curId);
70
            if (dsu.d[curId + 1].fa)
71
                dsu.merge(curId, curId + 1);
72
            if (dsu.d[curId - 1].fa)
73
                dsu.merge(curId, curId - 1);
74
        }
75
        ans[a[i].id] = ((maxb <= a[i].b - 1) ? 1 : 0);
76
    }
77
    for (int i = 1; i <= m; i++) {
78
        cout << ans[i] << endl;
79
    }
80
}

实际上，对于多次询问，若存在：

如果询问 $s_1$ 中，元素 $e_1$ 会对该询问的结果产生影响，那么对于所有弱于（或强于） $s_1$ 的 $s_2$ ，元素 $e_1$ 会对该询问的结果产生影响．

可以考虑使用离线处理 + 排序解决，此时处理后者时可以保留对前者的影响．

音乐

音乐