CF1168C
Ps：链接为洛谷OJ。
发现对于每一个 \(i\) 需要求经过若干次转移使第 \(j\) 个二进制位为 \(1\) 的最近位置 \(k\)，查询时，当 \(k \leq y\) 便可以到达。
下文的位无特殊说明位均指二进制位。
设 \(f[i][j]\) 为 \(i\) 经过转移使第 \(j\) 位为 \(1\) 的最近点，易得有如下转移方程：
\[f[i][j]=\min(f[i][j],f[k][j])\ \
(\begin{cases}
i < k\\
a_i\&a_k>0
\end{cases})
\]
方程需要逆序转移即从 \(n\) 到 \(1\) 转移。
时间复杂度 \(O(n^2log_2n)\)。
考虑优化，发现 \(i\) 的某一位到达的点可能有多个，但只需通过最近的一个进行转移。（最近的点已经转移到更远的点了）
可以维护一个 \(log_2n\) 的数组 \(g\)，\(g[j]\) 表示当前第 \(j\) 位相同，离 \(i\) 最近的点。
每次把 \(a_i\) 中位为 \(1\) 的第 \(j\) 的 \(g[j]\) 赋为 \(i\) 即可。
时间复杂度 \(O(nlog^2_2(n))\)。
具体实现看代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
int n,q;
int f[maxn][30],a[maxn],top[30];//top为维护某位最近点的数组
bool vis[maxn][30];//标记i的第j位是否为1
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
int tmp=a[i],ct=0;
while(tmp)
{
vis[i][ct]=tmp%2;
tmp/=2;
ct++;
}
}
memset(f,0x7f,sizeof(f));
for(int i=0;i<=20;i++) top[i]=n+1,f[n+1][i]=n+1;
for(int i=n;i;i--)
{
for(int j=20;j>=0;j--)
{
if(!vis[i][j]) continue;
f[i][j]=i;
int u=top[j];
for(int k=20;k>=0;k--) f[i][k]=min(f[i][k],f[u][k]);
top[j]=i;
}
}
while(q--)
{
int x,y;
bool flg=0;
scanf("%d%d",&x,&y);
for(int i=0;i<=20;i++)
{
if(vis[y][i]&&f[x][i]<=y)
{
flg=1;
break;
}
}
if(flg) printf("Shi\n");
else printf("Fou\n");
}
}