题目呈现

P9100 Miny#

题目描述#

$n$ 枚地雷被运到 Bytau 的军事训练场，并沿一条直线埋设．每个地雷位于不同的地方，并且有自己的爆炸半径．当引爆时，地雷会自动引爆其爆炸半径内所有尚未爆炸的地雷．如果地雷 $a$ 和地雷 $b$ 之间的距离不超过地雷 $b$ 的爆炸半径，则我们称地雷 $a$ 在地雷 $b$ 的爆炸半径内．

Bytomir 中士想进行一项实验．他选择了一个任意的地雷子集（也许是空的），并让这个地雷子集内的所有地雷在同时手动引爆．实验的结果是一组已经爆炸的地雷——要么是手动引爆的引起的爆炸，要么是其他地雷爆炸导致的爆炸．

Bytomir 能得到多少种可能的实验结果？如果两个实验结果中爆炸的地雷相同，则这两个实验结果是相同的．由于结果可能很大，请输出它除以 $10^9+7$ 的余数．

输入格式#

输入第一行包含一个整数 $n$ ，表示地雷个数．

接下来 $n$ 行，每行两个整数 $a_i,r_i$ ，分别表示地雷的位置和爆炸半径．你可以假设 $a_1<a_2<\cdots<a_n$ ．

输出格式#

输出可能的实验结果总数对 $10^9+7$ 取模后的值．

输入输出样例 #1#

输入 #1#

输出 #1#

1
7

说明/提示#

样例 1 解释#

你可以得到 $7$ 种可能的实验结果：

$\{\}$ （空集）：如果不引爆任何地雷；
$\{1,2\}$ （地雷 $1,2$ ）：如果我们只引爆地雷 $1$ ；
$\{1,2,3\}$ ：如果我们引爆地雷 $1$ 和 $3$ ；
$\{1,2,3,4\}$ ：如果我们引爆地雷 $1$ 和 $4$ ；
$\{2\}$ ：如果我们只引爆地雷 $2$ ；
$\{2,3\}$ ：如果我们只引爆地雷 $3$ ；
$\{2,3,4\}$ ：如果我们只引爆地雷 $4$ ；

请注意，可以通过不同的方式得到同一个实验结果——例如，如果我们引爆地雷 $1$ 和 $2$ ，也会得到 $\{1, 2\}$ 的结果．

数据范围#

本题采用捆绑测试

对于 $50\%$ 的数据，保证 $1\le n\le 5000$ ．

对于 $100\%$ 的数据，保证 $1\le n\le 3\times 10^5$ ， $0\le a_i,r_i\le 10^{18}$ ．

先来解决小数据．

由于小数据数据范围较少，考虑 dp，这里定义 dp[i] 表示考虑到第 $i$ 个地雷，且第 $i$ 个地雷不被引爆的方案数，这样 dp 可以使得第 $i$ 个地雷（及以前的所有地雷）都不会引爆第 $i$ 个地雷之后的所有地雷，从而满足无后效性．

显然，有初始状态：dp[0] = 1，即不选择地雷，则存在没有地雷爆炸这一种情况．

考虑转换方程：dp[i] 可以由 dp[j] 转换而来（ $j<i$ ），当且仅当手动引爆第 $[i+1,j-1]$ 个地雷时，地雷 $i$ 和 $j$ 都不会被引爆．

为了满足这两颗地雷都不会被引爆，我们需要保证：

地雷 $i$ 左边第一个会引爆 $i$ 的地雷不在区间 $[i+1,j-1]$ 之中．（保证地雷 $i$ 不会被引爆）
地雷 $j$ 右边第一个会引爆 $j$ 的地雷不在区间 $[i+1,j-1]$ 之中．（保证地雷 $i$ 不会被引爆）

即，设地雷 $i$ 左边第一个会引爆 $i$ 的地雷为 $L_i$ ，地雷 $i$ 右边第一个会引爆 $i$ 的地雷为 $R_i$ ．则符合条件的 $j$ 满足：

$j<i$
$L_i\leq j$
$i\leq R_j$

，从 $i-1$ 开始向前遍历直到 $L_i$ ，寻找合法的 $j$ 加入贡献即可．

在计算 $L_i$ 时，从 $i-1$ 开始向前遍历，找到第一个 $a_j + r_j \geq a_i$ 的地雷， $L_i=j$ ．同理，在计算 $R_i$ 时，从 $i+1$ 开始向前遍历，找到第一个 $a_j - r_j \leq a_i$ 的地雷， $L_i=j$ ．

在统计最终状态时，可以引入哨兵，在地雷序列首位和末尾各增加一个距离无限远、爆炸半径无限远（可以炸到另外一个哨兵）的哨兵地雷 $0$ 和 $n+1$ ．从而使得 $\forall i \in [1, n]$ ， $L_i$ 和 $R_i$ 都不为空，同时，dp[n+1] 还能收集到所有未贡献状态（即 $\forall j\in [0, n],R_j=n+1$ 的状态 dp[j]）．

最终状态即为 dp[n+1]．

$50pts$ 标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
const int N = 3e5 + 100;
5
const int MOD = 1e9 + 7;
6
int n, a[N], r[N], dp[N], L[N], R[N];
7

8
signed main() {
9
#ifdef ONLINE_JUDGE
10
    freopen("landmine.in", "r", stdin);
11
    freopen("landmine.out", "w", stdout);
12
#endif
13
    cin >> n;
14
    for (int i = 1; i <= n; i++) {
15
        cin >> a[i] >> r[i];
16
    }
17
    a[n + 1] = 2e18;
18
    r[n + 1] = 4e18 + 10; // LLONG_MAX 约为 9e18
19
    a[0] = -2e18;
20
    r[0] = 4e18 + 10;
21
    for (int i = 0; i <= n + 1; i++) {
22
        for (int j = 0; j < i; j++) {
23
            if (a[j] + r[j] >= a[i]) {
24
                L[i] = j;
25
            }
26
        }
27
    }
28
    memset(R, 0x3f, sizeof(R));
29
    for (int i = 0; i <= n + 1; i++) {
30
        for (int j = i + 1; j <= n + 1; j++) {
31
            if (a[j] - r[j] <= a[i]) {
32
                R[i] = min(j, R[i]);
33
            }
34
        }
35
    }
36
    dp[0] = 1;
37
    for (int i = 0; i <= n + 1; i++) {
38
        for (int j = L[i]; j < i; j++) {
39
            if (i <= R[j]) {
40
                (dp[i] += dp[j]) %= MOD;
41
            }
42
        }
43
    }
44
    cout << dp[n + 1];
45
    return 0;
46
}

这样的复杂度是 $O(n^2)$ 的，考虑如何优化．

首先，预处理 $L_i$ 和 $R_i$ 可以使用 ST 表和二分进行优化．以计算 $L_i$ 为例，具体来说，对于区间 $[l,r]$ ，二分可能的子区间 $i\in [mid,r]$ ，对于该子区间，求出 $a[i]+r[i]$ 的最大值（即每个地雷最右影响位置）是否比 $a_i$ 大（或等于），如果是，说明 $L_i$ 在该子区间内，在该子区间内继续二分，否则，在相反的子区间 $[l, mid-1]$ 内进行二分． $R_i$ 的处理和 $L_i$ 相类似．

ST 表实现如下：

1
struct ST {
2
    int *p;
3
    int fmax[32][N];
4
    int fmin[32][N];
5
    ST(int *p) : p(p) {}
6
    void init(int size) {
7
        for (int i = 0; i <= size; i++) {
8
            fmax[0][i] = p[i];
9
            fmin[0][i] = p[i];
10
        }
11
        for (int j = 1; j <= 30; j++) {
12
            for (int i = 0; i + (1 << (j - 1)) <= size; i++) {
13
                fmax[j][i] =
14
                    max(fmax[j - 1][i], fmax[j - 1][i + (1 << (j - 1))]);
15
                fmin[j][i] =
16
                    min(fmin[j - 1][i], fmin[j - 1][i + (1 << (j - 1))]);
17
            }
18
        }
19
    }
20
    int mini(int l, int r) {
21
        int len = log(r - l + 1) / log(2);
22
        return min(fmin[len][l], fmin[len][r - (1 << len) + 1]);
23
    }
24
    int maxi(int l, int r) {
25
        int len = log(r - l + 1) / log(2);
26
        return max(fmax[len][l], fmax[len][r - (1 << len) + 1]);
27
    }
28
};
29

30
ST l_st(l_lim), r_st(r_lim);

预处理实现如下：

1
for (int i = 0; i <= n + 1; i++) {
2
  l_lim[i] = a[i] - r[i];
3
  r_lim[i] = a[i] + r[i];
4
}
5

6
l_st.init(n + 1), r_st.init(n + 1);
7

8
for (int i = 0; i <= n + 1; i++) {
9
  int l = 0, r = i - 1, ans = 0;
10
  while (l <= r) {
11
    int mid = (l + r) / 2;
12
    if (r_st.maxi(mid, r) >= a[i]) {
13
      ans = mid;
14
      l = mid + 1;
15
    } else {
16
      r = mid - 1;
17
    }
18
  }
19
  L[i] = ans;
20
}
21
for (int i = 0; i <= n + 1; i++) {
22
  int l = i + 1, r = n + 1, ans = n + 1;
23
  while (l <= r) {
24
    int mid = (l + r) / 2;
25
    if (l_st.mini(l, mid) <= a[i]) {
26
      ans = min(ans, mid);
27
      r = mid - 1;
28
    } else {
29
      l = mid + 1;
30
    }
31
  }
32
  R[i] = ans;
33
}

再考虑如何优化 dp．

dp 的转移方程中涉及到区间加和的问题，因此可以将 $dp$ 数组放入树状数组优化．在每一次计算 $dp[i]$ 时，计算 $j\in [L_i,i-1]$ 之和，再减去所有不满足 $i\leq R_j$ 的 $j$ ．

怎么减去呢？要减去的 $j$ 满足 $R_j < i$ ，显然，当一项需要被减去之后（ $R_j=i$ ），该项就不会再对之后的计算产生贡献（ $R_j \geq i+k,k\in\mathbb{N}^+$ ）．因此，在每一次计算完 $dp[i]$ 之后，将所有的 $j$ 满足 $R_j=i$ 的 $dp[j]$ 在树状数组中删除（即设为 0）（查找满足要求的 $j$ 可以使用 map），这样，在后续进行计算时，该项就不会被计入贡献．

1
map<int, vector<int>> r_R;
2

3
// 树状数组实现
4
struct BIT {
5
    int c[N];
6
    int size;
7
    int lowbit(int i) { return i & (-i); }
8
    BIT() { memset(c, 0, sizeof(c)); }
9

10
    void init(int size) { this->size = size; }
11
    void upd(int p, int v) {
12
        p++; // 转为 1-based
13
        for (int i = p; i <= size; i = i + lowbit(i)) {
14
            (c[i] += v + MOD) %= MOD;
15
        }
16
    }
17
    int qry(int p) {
18
        p++; // 转为 1-based
19
        int ans = 0;
20
        for (int i = p; i >= 1; i -= lowbit(i)) {
21
            (ans += c[i]) %= MOD;
22
        }
23
        return ans;
24
    }
25
    int qry(int l, int r) { return qry(r) - qry(l - 1); }
26
};
27
BIT bit;

main 函数内：

1
bit.upd(0, 1);
2
dp[0] = 1;
3
for (int i = 1; i <= n + 1; i++) {
4
  (dp[i] += bit.qry(L[i], i - 1)) %= MOD;
5
  bit.upd(i, dp[i]);
6
  vector<int> &vec = r_R[i];
7
  for (int j = 0; j < vec.size(); j++) {
8
    int ori = bit.qry(vec[j], vec[j]);
9
    bit.upd(vec[j], -ori);
10
  }
11
}

$100pts$ 标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
const int N = 3e5 + 100;
5
const int MOD = 1e9 + 7;
6
int n, a[N], r[N], dp[N], L[N], R[N], l_lim[N], r_lim[N];
7
map<int, vector<int>> r_R;
8

9
struct ST {
10
    int *p;
11
    int fmax[32][N];
12
    int fmin[32][N];
13
    ST(int *p) : p(p) {}
14
    void init(int size) {
15
        for (int i = 0; i <= size; i++) {
16
            fmax[0][i] = p[i];
17
            fmin[0][i] = p[i];
18
        }
19
        for (int j = 1; j <= 30; j++) {
20
            for (int i = 0; i + (1 << (j - 1)) <= size; i++) {
21
                fmax[j][i] =
22
                    max(fmax[j - 1][i], fmax[j - 1][i + (1 << (j - 1))]);
23
                fmin[j][i] =
24
                    min(fmin[j - 1][i], fmin[j - 1][i + (1 << (j - 1))]);
25
            }
26
        }
27
    }
28
    int mini(int l, int r) {
29
        int len = log(r - l + 1) / log(2);
30
        return min(fmin[len][l], fmin[len][r - (1 << len) + 1]);
31
    }
32
    int maxi(int l, int r) {
33
        int len = log(r - l + 1) / log(2);
34
        return max(fmax[len][l], fmax[len][r - (1 << len) + 1]);
35
    }
36
};
37

38
struct BIT {
39
    int c[N];
40
    int size;
41
    int lowbit(int i) { return i & (-i); }
42
    BIT() { memset(c, 0, sizeof(c)); }
43

44
    void init(int size) { this->size = size; }
45
    void upd(int p, int v) {
46
        p++; // 转为 1-based
47
        for (int i = p; i <= size; i = i + lowbit(i)) {
48
            (c[i] += v + MOD) %= MOD;
49
        }
50
    }
51
    int qry(int p) {
52
        p++; // 转为 1-based
53
        int ans = 0;
54
        for (int i = p; i >= 1; i -= lowbit(i)) {
55
            (ans += c[i]) %= MOD;
56
        }
57
        return ans;
58
    }
59
    int qry(int l, int r) { return qry(r) - qry(l - 1); }
60
};
61

62
ST l_st(l_lim), r_st(r_lim);
63
BIT bit;
64

65
signed main() {
66
#ifdef ONLINE_JUDGE
67
    freopen("landmine.in", "r", stdin);
68
    freopen("landmine.out", "w", stdout);
69
#endif
70
    cin >> n;
71
    for (int i = 1; i <= n; i++) {
72
        cin >> a[i] >> r[i];
73
    }
74
    a[n + 1] = 2e18;
75
    r[n + 1] = 4e18 + 10;
76
    a[0] = -2e18;
77
    r[0] = 4e18 + 10;
78
    for (int i = 0; i <= n + 1; i++) {
79
        l_lim[i] = a[i] - r[i];
80
        r_lim[i] = a[i] + r[i];
81
    }
82

83
    l_st.init(n + 1), r_st.init(n + 1);
84
    bit.init(n + 1);
85

86
    for (int i = 0; i <= n + 1; i++) {
87
        int l = 0, r = i - 1, ans = 0;
88
        while (l <= r) {
89
            int mid = (l + r) / 2;
90
            if (r_st.maxi(mid, r) >= a[i]) {
91
                ans = mid;
92
                l = mid + 1;
93
            } else {
94
                r = mid - 1;
95
            }
96
        }
97
        L[i] = ans;
98
    }
99
    for (int i = 0; i <= n + 1; i++) {
100
        int l = i + 1, r = n + 1, ans = n + 1;
101
        while (l <= r) {
102
            int mid = (l + r) / 2;
103
            if (l_st.mini(l, mid) <= a[i]) {
104
                ans = min(ans, mid);
105
                r = mid - 1;
106
            } else {
107
                l = mid + 1;
108
            }
109
        }
110
        R[i] = ans;
111
        r_R[R[i]].push_back(i);
112
    }
113
    bit.upd(0, 1);
114
    dp[0] = 1;
115
    for (int i = 1; i <= n + 1; i++) {
116
        (dp[i] += bit.qry(L[i], i - 1)) %= MOD;
117
        bit.upd(i, dp[i]);
118
        vector<int> &vec = r_R[i];
119
        for (int j = 0; j < vec.size(); j++) {
120
            int ori = bit.qry(vec[j], vec[j]);
121
            bit.upd(vec[j], -ori);
122
        }
123
    }
124
    cout << dp[n + 1];
125
    return 0;
126
}

音乐

音乐

P9100 Miny#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

说明/提示#

样例 1 解释#

数据范围#

文章分享

音乐

安吉D5-T3

P9100 Miny#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

说明/提示#

样例 1 解释#

数据范围#

文章分享