And Reachability

题面翻译

题目描述

Toad Pimple 有一个整数数组 $a_1,\dots,a_n$。
当 $x < y$ 且存在 $x = p_1 < \dots < p_k = y$ 的数列 $p$ 满足 $a_{p_i} \& a_{p_{i+1}} > 0$ 时，我们称 $y$ 是可从 $x$ 到达的。
其中 $\&$ 表示按位与运算。

现在给出 $q$ 组下标，请检查它们可否到达。

输入输出格式

输入格式：

第一行，两个整数 $n,q\;(2 \le n \le 300\,000,1 \le q \le 300\,000)$，表示数组的长度和查询的个数。
第二行，$n$ 个整数 $a_1,\dots,a_n\;(0 \le a_i \le 300\;000)$，表示给定的数组。
接下来 $q$ 行中，第 $i$ 行两个整数 $x_i,y_i\;(1 \le x_i < y_i \le n)$，表示你需要检查 $y_i$ 是否可从 $x_i$ 到达。

输出格式：

输出 $q$ 行。
对于每个询问，如果可到达，输出「Shi」，否则输出「Fou」。

说明

第一个样例中，$a_3 = 0$，与其按位与结果总是 $0$，所以不可到达。
$a_2 \& a_4 > 0$，所以 $4$ 可从 $2$ 到达。
并且从 $1$ 到达 $4$ 中，$p = [1,2,4]$。

题目描述

Toad Pimple has an array of integers $ a_1, a_2, \ldots, a_n $ .

We say that $ y $ is reachable from $ x $ if $ x<y $ and there exists an integer array $ p $ such that $ x = p_1 < p_2 < \ldots < p_k=y $ , and $ a_{p_i}, &, a_{p_{i+1}} > 0 $ for all integers $ i $ such that $ 1 \leq i < k $ .

Here $ & $ denotes the bitwise AND operation.

You are given $ q $ pairs of indices, check reachability for each of them.

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 2 \leq n \leq 300,000 $ , $ 1 \leq q \leq 300,000 $ ) — the number of integers in the array and the number of queries you need to answer.

The second line contains $ n $ space-separated integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i \leq 300,000 $ ) — the given array.

The next $ q $ lines contain two integers each. The $ i $ -th of them contains two space-separated integers $ x_i $ and $ y_i $ ( $ 1 \leq x_i < y_i \leq n $ ). You need to check if $ y_i $ is reachable from $ x_i $ .

输出格式

Output $ q $ lines. In the $ i $ -th of them print "Shi" if $ y_i $ is reachable from $ x_i $ , otherwise, print "Fou".

样例 #1

样例输入 #1

样例输出 #1

Fou
Shi
Shi

提示

In the first example, $ a_3 = 0 $ . You can't reach it, because AND with it is always zero. $ a_2, &, a_4 > 0 $ , so $ 4 $ is reachable from $ 2 $ , and to go from $ 1 $ to $ 4 $ you can use $ p = [1, 2, 4] $ .

有关位运算，按位考虑。

如果改 $x$ 的时候出现了某一个 $y$ 也有的位，那就可以直接跳到 $y$ 了。

那么定义 $d_{i,j}$ 为第 $i$ 个数，要跳到一个拥有第 $j$ 位的数，最前是跳到哪一个。

然后倒着枚举 $i$，找到一个这个数跳到拥有第 $k$ 位的到哪里，然后转移 d 数组。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int read()
{
	int s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s;
}
int n,q,a[N],mx,nx[20][20],ds[N][20];
int main()
{
//	freopen("and.in","r",stdin);
//	freopen("and.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=0;i<=18;i++)
		for(int j=0;j<=18;j++)
			nx[i][j]=n+1;
	for(int j=0;j<=18;j++)
		ds[n+1][j]=n+1;
	for(int i=n;i;i--)
	{
		for(int j=0;j<=18;j++)
		{
			if(a[i]>>j&1)
				ds[i][j]=i;
			else
				ds[i][j]=n+1;
		}
		for(int j=0;j<=18;j++)
			for(int k=0;k<=18;k++)
				if((a[i]>>j&1)&&(a[i]>>k&1))
					nx[j][k]=i;
		for(int j=0;j<=18;j++)
		{
			int mn=n+1;
			for(int k=0;k<=18;k++)
				if(a[i]>>k&1)
					mn=min(mn,nx[j][k]);
			for(int k=0;k<=18;k++)
				ds[i][k]=min(ds[i][k],ds[mn][k]);
		}
//		for(int j=0;j<=7;j++)
//			printf("%d ",ds[i][j]);
//		puts(""); 
	}
	while(q--)
	{
		int fl=0,x=read(),y=read();
		for(int i=0;i<=18;i++)
			if(ds[x][i]<=y&&(a[y]>>i&1))
				fl=1,puts("Shi"),i=18;
		if(!fl)
			puts("Fou");
	}
}