题目链接
https://codeforces.com/problemset/problem/1168/C
题目大意
给定一个数组 \(a\)，从下标 \(x\) 能够转移到下标 \(y\) 要满足 \(x \lt y\) 且 \(a_{p_i}\, \&\, a_{p_{i+1}} > 0\)，其中 \(\&\) 表示逻辑与。多次询问，每次询问给出 \(x\) 和 \(y\)，你需要回答出能够通过若干次转移从下标 \(x\) 到达下标 \(y\)。
解题思路
定义 \(go_{i, k}\) 表示从下标 \(i\) 能够到达的最小的下标 \(j\)，且满足 \(a_j\) 的第 \(k\) 位为 \(1\)（这里 \(j \ge i\)）。
如何计算它呢？再定义一个 \(last_{i,k}\) 表示满足 \(j \gt i\) 且 \(a_j\) 的第 \(k\) 位为 \(1\) 的最小下标 \(j\)。
可以证明 \(go_{i,k}\) 等于 \(i\) 或者 \(\min{(go_{last_{i,j},k})}\) （其中 \(j\) 对应的是 \(a_i\) 为 \(1\) 的所有那些位）。
所以在 \(O(n \log \max\{a_i\})\) 时间复杂度只能能够求出所有的状态 \(go_{i, k}\)。然后只要对于 \(a_y\) 中为 \(1\) 的任意一位 \(j\) 来说，只要满足 \(go_{x, j} \leq y\) 就能从下标 \(x\) 转移到下标 \(y\)。
示例程序
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
int n, q, a[maxn], last[19], go[maxn][19];
bool check(int x, int y) {
for (int i = 0; i < 19; i++)
if (go[x][i] <= y && (a[y] & (1 << i)))
return true;
return false;
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", a+i);
for (int i = 0; i < 19; i++) go[n+1][i] = last[i] = n+1;
for (int i = n; i >= 1; i--) {
for (int j = 0; j < 19; j++)
go[i][j] = n + 1;
for (int j = 0; j < 19; j++) {
if (a[i] & (1 << j)) {
for (int k = 0; k < 19; k++) {
go[i][k] = min(go[i][k], go[ last[j] ][k]);
}
last[j] = i;
go[i][j] = i;
}
}
}
while (q--) {
int x, y;
scanf("%d%d", &x, &y);
puts(check(x, y) ? "Shi" : "Fou");
}
return 0;
}