题目链接
题目思路
设\(dp[i][j]\)表示\(a[i]\)走到二进制第\(j\)位为\(1\)的数的最近点的在哪里
然后转移求解即可，比较巧妙
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=3e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,q;
int a[maxn];
int last[30];
int dp[maxn][30];
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
memset(last,0x3f,sizeof(last));
memset(dp,0x3f,sizeof(dp));
for(int i=n;i>=1;i--){
for(int j=0;j<=20;j++){
if(a[i]&(1<<j)){
dp[i][j]=i;
}else{
for(int k=0;k<=20;k++){
if((a[i]&(1<<k))&&last[k]!=inf){
dp[i][j]=min(dp[i][j],dp[last[k]][j]);
}
}
}
}
for(int j=0;j<=20;j++){
if(a[i]&(1<<j)){
last[j]=i;
}
}
}
for(int i=1,l,r;i<=q;i++){
scanf("%d%d",&l,&r);
bool flag=0;
for(int j=0;j<=20;j++){
if(a[r]&(1<<j)){
if(dp[l][j]<=r){
flag=1;
break;
}
}
}
printf(flag?"Shi\n":"Fou\n");
}
return 0;
}