1. E - 滑动窗口
https://atcoder.jp/contests/abc260/tasks/abc260_e
1.1 Problem Statement
给定整数 $M$ 和 $N$ 个整数对: $(A_1, B_1), (A_2, B_2),…, (A_N, B_N)$, 满足: $1 \le A_i \le B_i \le M$
Good Sequence
:
$S$ is a contiguous subsequence of the sequence $(1,2,3,…,M)$
For all i, S contains at least one of $A_i$ or $B_i$
Let $f(k)$ be the number of possible good sequences of length $k$
Enumerate $f(1), f(2), …, f(M)$
1.2 分析
把排列 $(1, 2, 3, …, M)$ 中连续的一个区间称作 $[l, r]$
如下性质:
设: $1 \le i, j, k, l \le M$, 如果区间 $[k, l]$ 包含区间 $[i, j]$, 即$k \le i \le j \le l$
那么, 如果区间 $[i, j]$ 满足要求, 区间$[k, l]$ 也满足要求
滑动窗口
:
首先, 令: $L = R = 1$
当满足 $L \le M$:
区间 $[L, R]$ 满足要求, 移动右边界: $R \leftarrow R + 1$
区间 $[L, R]$ 满足要求, 则区间 $[L, x] (R \le x \le M)$ 都满足要求, 更新答案
移动区间左边界: $L \leftarrow L + 1$
1.3 code
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
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, M;
cin >> N >> M;
vector<int> A(N), B(N);
for (int i = 0; i < N; i++) {
cin >> A[i] >> B[i];
}
vector<vector<int>> inv(M + 1);
for (int i = 0; i < N; i++) {
inv[A[i]].push_back(i);
inv[B[i]].push_back(i);
}
vector<int> cnt(N), ans(M + 3);
// 表示没有被区间 [i, j] 包围的区间 [a, b]的数量(a与b都不出现在区间[i, j]内)
int cnt_zero = N;
for (int i = 1, j = 1; i <= M;) {
// 不断扩展右边界 `j`
while (j <= M and cnt_zero != 0) {
// 新的区间右边界 `j` 可以将下标集合inv[j]中的左右集合都覆盖
for (auto & x : inv[j]) {
// 如果是第一次覆盖, 没有被覆盖的区间数量减一
if (cnt[x] == 0) cnt_zero--;
// 表示区间x被覆盖
cnt[x]++;
}
j++;
}
// 区间[i, j]不能把所有区间全部覆盖, 失败
if (cnt_zero != 0)
{
break;
}
// 差分数组
ans[j - i]++;
ans[M + 1 - i + 1]--;
// 左边界 `i` 向右移一格
for (auto & x : inv[i]) {
// 把区间左边界 `i` 能覆盖的区间全部移除
cnt[x]--;
// 此时区间x不能被区间[i, j]覆盖
if (cnt[x] == 0) cnt_zero++;
}
i++;
}
for (int i = 1; i <= M; i++) {
ans[i] += ans[i - 1];
cout << ans[i] << " \n"[i == M];
}
}