【2022 NOIP 多校联测 2】划船 做题记录

$n$ 个点，$m$ 条有向边，每条有向边 $u_i,v_i$ 满足 $1\le u_i<v_i\le u_i+k$。$q$ 组询问，每次给定两个点 $x,y$ 满足 $x\le y$，判断是否能从 $x$ 走到 $y$，强制在线。

$1\le n,m\le 2\times10^5$，$1\le k\le 200$。

对于一个区间 $[l,r]$，设 $mid=\lfloor\frac{l+r}{2}\rfloor$，则想要从 $[l,mid]$ 去 $[mid+1,r]$ 就一定要经过 $[mid,\min(mid+k,r)]$ 中的至少一个点，所以可以分治预处理出每个区间中左半部分的点能到 $[mid,\min(mid+k,r)]$ 中的哪些点，右半部分的点能由哪些点到达，用 bitset 维护一下。查询的时候直接找到对应的区间把 bitset 按位与一下即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <bitset>
#include <vector>

using namespace std;

const int S=200005;

int n,m,k;
vector<int> g[S];
bitset<205> dp[25][S];
int q;

void init(int l,int r,int d)
{
	if(l==r) return;
	int mid=l+r>>1;
	for(int i=mid;i<=min(mid+k,r);i++) dp[d][i][i-mid]=1;
	for(int u=mid-1;u>=l;u--) for(int v:g[u]) if(v<=r) dp[d][u]|=dp[d][v];
	for(int u=mid;u<=r;u++) for(int v:g[u]) if(v<=r) dp[d][v]|=dp[d][u];
	init(l,mid,d+1),init(mid+1,r,d+1);
}

bool que(int l,int r,int d,int s,int t)
{
	int mid=l+r>>1;
	if(t<=mid) return que(l,mid,d+1,s,t);
	else if(mid<s) return que(mid+1,r,d+1,s,t);
	return (dp[d][s]&dp[d][t]).any();
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
	}
	init(1,n,0);
	scanf("%d",&q);
	int c=0;
	while(q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		x=((1ll*c*c)^x)%n+1,y=((1ll*c*c)^y)%n+1;
		if(x>y) swap(x,y);
		if(x==y||que(1,n,0,x,y)) c++,puts("Yes");
		else puts("No");
	}
	return 0;
}