Codeforces Round #562 (Div. 2) E. And Reachability(dp)

题目

n(n<=3e5)个整数，第i个数为ai(0<=ai<=3e5)，1<=i<=n

如果(ai&aj)>0，则称i到j是可达的，i<j

q(q<=3e5)个询问，每次询问两个下标x和y(x<y)，

问在允许中间插入若干个下标位于[x+1,y-1]之间且插入序列单增的ai跳板的情况下，x到y是否可达

例如，ax ai aj ay是插入跳板之后的序列，

那么x到y可达当且仅当x到i可达，i到j可达，j到y可达，且下标满足x<i<j<y

思路来源

Codeforces Round #562 — Editorial

题解

last[i][k]记录大于i的最小下标j，满足aj在二进制表示下第k位为1

go[i][k]记录大于等于i的最小下标j，满足aj在二进制表示下第k位为1，且从i可达

倒着dp，可以把last数组求出来，如果last[i-1][k]能被ai的对应位更新就更新，否则last[i-1][k]沿用last[i][k]

①如果ai在第k位为1，go[i][k]=i显然成立

②ai自己没有第k位，却要去一个有第k位的最小的位置，

那么它只能，先以自己有的二进制位k为跳板，去到last[i][k]对应的下标j，

再去利用go[j][k]，寄希望于aj有第k位，或再重复该跳板过程，到达一个有第k位的最小的位置，

多条j的路径都可以更新go[i][k]的值，于其中取小即为go[i][k]

查询问x是否可达y时，只需检查y的所有二进制为1的位k，

若存在k使得go[x][k]<=y，即说明x->go[x][k]->y，可达；

所有都不符合，则不可达

心得

开始WA了一发，注意初始化

感觉自己思维题还是练的不够吧

但所幸现在能照着turorial大致敲出来，码力还凑活

相信随着积累应该是可以渐渐培养思维的

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
const int lg=20;
int go[maxn][lg],last[maxn][lg];
int n,q,a[maxn];
int b[lg],cnt;
int x,y;
bool ok()
{
	for(int k=19;k>=0;--k)
	{
		if(!(a[y]>>k&1))continue;
		if(go[x][k]<=y)return 1;
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i)
	scanf("%d",&a[i]);
	for(int i=n+1;i>=1;--i)//go[last[i][b[j]]][k]会用到go[n+1][k] 
	{
		for(int k=19;k>=0;--k)
	    go[i][k]=last[i][k]=n+1;
	}
	for(int i=n;i>=1;--i)
	{
		for(int k=19;k>=0;--k)
		{
			if(a[i]>>k&1)last[i-1][k]=i;//对于上一个位置来说,最小一定是本位置 
			else last[i-1][k]=last[i][k];
			//printf("last[%d][%d]:%d\n",i-1,k,last[i-1][k]);
	    }
	}
	for(int i=n;i>=1;--i)
	{
		cnt=0;
		for(int k=19;k>=0;--k)
		{
			if(a[i]>>k&1)
		 	{
			  go[i][k]=i;
		 	  b[cnt++]=k;
	   		}
		} 
	    for(int k=19;k>=0;--k)
	    {
	    	if(a[i]>>k&1)continue;
	    	for(int j=0;j<cnt;++j)
	    	go[i][k]=min(go[i][k],go[last[i][b[j]]][k]);
	    }
	} 
	while(q--)
	{
		scanf("%d%d",&x,&y);
		puts(ok()?"Shi":"Fou");
	}
	return 0;
}