Codeforces 1168C And Reachability
题目链接
https://codeforces.com/contest/1168/problem/C
题目大意
给你一个长度为 $n$ 的数列 $a$ ，$q$ 次询问，问是否存在数列 $p$ 使得有 $x=p_1<p_2<\cdots<p_k=y$，且 $a_{p_i} \& a_{p_{i+1}}>0(1 \leq i < k)$ 成立。
题目分析
看到有 $q$ 次询问，可以想到需要预处理一些东西之后迅速查询。观察给的式子，可以发现，如果 $a_x$ 能走到 $a_y=2^i$ ，那么所有包含 $2^i$ 且位置大于等于 $y$ 的都可以走到。因此显然可以将所有的位拆解，对于每一个位置求走到 $2^i$ 的最小需要的右端点位置。求这个显然只需要记录一下每一位出现的最后一次的位置，再 $DP$ 一下就可以。
查询的时候枚举一下是通过哪个 $2^i$ 走过去的，判断一下右端点位置是否满足要求即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
const int inf = 0x3f3f3f3f;
int n, m;
int a[maxn];
int f[maxn][21];
int last[21];
int main(){
int i, j, k;
int x, y;
memset(f, 0x3f, sizeof(f));
memset(last, 0x3f, sizeof(last));
scanf("%d%d", &n, &m);
for(i=1;i<=n;i++){
scanf("%d", &a[i]);
}
for(i=n;i>0;i--){
for(j=0;j<=20;j++){
if((a[i] >> j) & 1){
f[i][j] = i;
if(last[j] != inf){
for(k=0;k<=20;k++){
f[i][k] = min(f[i][k], f[last[j]][k]);
}
}
last[j] = i;
}
}
}
while(m--){
scanf("%d%d", &x, &y);
bool flag = false;
for(j=0;j<=20;j++){
if((a[y] >> j) & 1){
if(y >= f[x][j]){
flag = true;
break;
}
}
}
if(flag){
printf("Shi\n");
}else{
printf("Fou\n");
}
}
return 0;
}