CF1168C And Reachability

CF1168C And Reachability

洛谷CF1168C And Reachability

题目大意

有一个数组$a_1,a_2,\cdots ,a_n$，我们称$x$到$y$可达当且仅当：

• $x<y$
• 存在一个数组$p$，其中$x=p_1<p_2<\cdots <p_k=y$，且对于任意$1\le i<k$，满足$a_{p_i}\&a_{p_i+1}>0$

有$q$组询问，第$i$组询问给出$x_i$和$y_i$，求它们是否可达。如果可达，输出$Shi$；否则，输出$Fou$。

$1\le n\le 3\times 10^5,1\le q\le 3\times 10^5,x_i<y_i$

题解

首先，如果$x$到$y$可达，$y$到$z$可达，则$x$到$z$可达。

对于一个点$i$，如果$a_i\&2^k>0$，则对于所有$j>i$且$a_j\&2^k>0$，$i$到$j$都是可达的。

设$w_{i,k}$表示$i$可达的最小的$j$（这里，我们定义当$a_i>0$时，$i$到$i$是可达的），那么，对于所有$j>i$，只要满足存在一个$k$使得$a_j\&2^k>0$且$w_{i,k}\le j$，则$i$到$j$可达。

那如何求$w_{i,k}$呢？对于每个$w_{i,k}$，我们只需求出满足$j>i$且$a_j\&2^k>0$的最小的$j$，对于每个$0\le t\le \log n$，都令$w_{i,k}=\min (w_{i,k},w_{j,k})$。

考虑$w_{i,k}$的初始值。如果$a_i\&2^k>0$，$w_{i,k}=i$；否则，$w_{i,k}=n+1$。

求出$w_{i,k}$之后，对于每组$x,y$，如果存在一个$k$使得$a_y\&2^k>0$且$w_{x,k}\le y$，输出$Shi$；否则，输出$Fou$。

时间复杂度为$O(n{\log }^{2}n)$。

code

#include
using namespace std;
int n,q,x,y,fl,a[300005],lst[20],w[300005][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++){	
		scanf("%d",&a[i]);
		for(int j=0;j<=19;j++){
			if((a[i]>>j)&1) w[i][j]=i;
			else w[i][j]=n+1;
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=0;j<=19;j++){
			if(!((a[i]>>j)&1)) continue;
			if(lst[j])
			for(int k=0;k<=19;k++){
				w[i][k]=min(w[i][k],w[lst[j]][k]);
			}
			lst[j]=i;
		}
	}
	while(q--){
		scanf("%d%d",&x,&y);
		fl=0;
		for(int i=0;i<=19;i++){
			if(((a[y]>>i)&1)&&w[x][i]<=y) fl=1;
		}
		if(fl) printf("Shi\n");
		else printf("Fou\n");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36