题解 CF 1142B【Lynyrd Skynyrd】


好久没写倍增和题解了,几天前打$\mathrm{CF}$恰好碰到这题,感觉是道倍增好题。
原先倍增除了$\mathrm{ST}$表和求$\mathrm{LCA}$以外只写过一道《开车旅行》(还是在悲伤的$\mathrm{NOIp \ 2018}$前写的)。就当是练练手吧。
下面进入正题(题目翻译略):

1 思路解析

这题……乍一看好像没办法一眼秒掉……
考虑把它拆分成多个$\mathrm{subtask}$来解决假装自己在打$\mathrm{NOIp}$水部分分

1.1 $\mathrm{subtask \; 1}$:只有一个询问,且询问$p$(不是循环移位)是否为$a$的子序列

这个应该简单……设$s_i$满足$p_{s_i} = i$,即$i$在$p$中的位置。用$s_i$替换$a_i$(执行赋值操作:a[i] = s[a[i]]),再想办法验证现在的$a$是否有一个子序列$1, 2, 3,\ldots,n$即可。

1.2 $\mathrm{subtask \; 2}$:只有一个题目中给定的询问

循环移位还是比较麻烦的。首先不难想到如果匹配的子序列的第$i$位(下文称为“前驱”)已经确定,那么第$i+1$位(下文称为“后继”)肯定越靠前越好。这样,每个位置的后继位置是唯一确定的,于是问题转化为是否存在一个$i(a_i = p_1, i \in [l, r])$,使得它的第$i-1$个后继也在给定的区间中。如果从前驱像后继连一条有向边,那么我们会得到一幅有向无环图,且每个点的出度至多为$1$。联系《开车旅行》,我们发现在这种图上“某个点的第$k$个后继”可以用倍增法求得,于是本$\mathrm{subtask}$得解。

1.3 $\mathrm{subtask \; 3}$:多组询问,询问要求子序列严格与$p$相同(而不是$p$的循环移位)

上一个$\mathrm{subtas}$启发我们:是否可以把问题转化成求有向无环图上点的后继。答案很显然:可以。
仿照刚刚的思路,前驱和后继连好点,每个左端点记录一下自己右边(包括自己)最接近自己的$p_1$的位置,倍增求出它的第$n-1$个后继的位置,判断其是否位于询问区间内即可。

1.4 $\mathrm{subtask \; 4}$:多组询问,且询问循环移位

考虑继续“改造”上一个$\mathrm{subtask}$。“循环移位”看上去很麻烦,其实反倒放宽了限制:给定区间内任何一个位置都有可能是子序列的起点。只要有任何一个位置的第$n-1$个后继再询问区间内,那么这次询问的答案就是1
预处理出每个位置的第$n-1$个后继,将它们的位置存进$\mathrm{ST}$表。每次询问查询给定区间所有满足要求的子序列终点最靠前的那一个的终点位置,如果它再给定区间内,则输出1;否则输出0

这样我们就嘴巴了本题。

2 代码实现

由于图的特殊性质,我们不需要邻接表或者邻接矩阵,一个数组即可。
还有需要注意的就是特判$m < n$无解(全部询问输出0)。详细内容参见代码。

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
#include <cstring>
#include <iostream>
#include <algorithm>

const int maxn = 200005, maxv = 200002;
//maxv是一个特殊的点,用来表示某个点的某个后继不在a中

int n, m, q;
int a[maxn], next[25][maxn], p[maxn << 1], s[maxn], pos[maxn]; //next存图,pos辅助建图
int st[25][maxn], lg[maxn]; //ST表辅助数组

int query(int p) { //处理每一个位置
for (int i = 21; i >= 0; --i)
if ((m - 1) & 1 << i)
p = next[i][p];
return p;
}

int main() {
std::cin >> m >> n >> q; //此处适应个人习惯,m和n村的东西相反
if (m > n) { //特判
while (q--) std::cout << '0';
std::cout << std::endl;
return 0;
}
for (int i = 1; i <= m; ++i)
std::cin >> p[i],
p[i + m] = p[i], //倍长p是为了建图方便
s[p[i]] = i;
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
for (int i = 1; i <= maxv; ++i)
pos[i] = next[0][i] = maxv; //初始化
for (int i = n; i >= 1; --i)
pos[a[i]] = i, //pos[i]表示最近的i的位置
next[0][i] = pos[p[s[a[i]] + 1]];
for (int i = 1; 1 << i <= n; ++i)
for (int j = 1; j <= maxv; ++j)
next[i][j] = next[i-1][next[i-1][j]];
//预处理ST表的lg数组
for (int i = 1; 1 << i <= n; ++i)
lg[1 << i] = i;
for (int i = 1; i <= n; ++i)
if (!lg[i]) lg[i] = lg[i - 1];
for (int i = 1; i <= n; ++i)
st[0][i] = query(i);
//预处理ST表
for (int i = 1; 1 << i <= n; ++i)
for (int j = 1; j <= n; ++j) {
int len = 1 << (i - 1);
if (len + j - 1 > n)
break;
st[i][j] = std::min(st[i - 1][j], st[i - 1][j + len]);
}
// 输出答案
while (q--) {
int l, r;
std::cin >> l >> r;
int temp = lg[r - l + 1], len = 1 << temp;
temp = std::min(st[temp][l], st[temp][r - len + 1]);
std::cout << (temp <= r ? '1' : '0');
}
std::cout << std::endl;
return 0;
}

 评论