题解：CF2118D2 Red Light, Green Light (Hard version)

前言

傻逼题，赛时就不应该把 D1 和 D2 分开写。

Solution

看到这题首先应该想到如何处理红灯的相关信息，因为只有红灯会改变运动方向。

于是我们可以先预处理

p_i

左边和右边第一个碰到红灯的位置，设为

L_i

和

R_i

，如果没有则

L_i=0

或

R_i=n+1

。左边的话找最大

j

满足

p_i+d_i\equiv p_j+d_j\pmod k,j<i

，右边的话找最小

j

满足

p_i-d_i\equiv p_j-d_j\pmod k,j>i

。然后把它当成一张图，

i\to L_i

和

i\to R_i

当成边，发现如果一个点在环内是出不去的，于是我们可以直接处理环。

还有一种方法是设

i\to R_{L_i}

为一次跳跃，此时直接倍增跳足够多次就可以判断是否在环内。

然后这题就做完了，这里提供后者的代码。

CPP

#include<bits/stdc++.h>
#include<cmath>
#define ll long long
#define ull unsigned long long
#define lll __int128
#define N 500010
#define For(i,a,b) for(ll i=a;i<=b;++i)
#define Rof(i,a,b) for(ll i=a;i>=b;--i)
#define ls (x<<1)
#define rs (x<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,r 
#define pb push_back
#define mk make_pair
#define pque priority_queue
#define pii pair<ll,ll>
#define fi first
#define se second

using namespace std;
set<ll >s[N];
ll p[N],d[N],c[N],tot=0,a[N];
ll T,n,k,q;

ll read(){	
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;		
}
map<ll ,ll >lst;
ll L[N],R[N],to[N][50];

void sol(){
	n=read(),k=read();
	For(i,1,n) p[i]=read();
	For(i,1,n) d[i]=read();
	For(i,0,49) to[0][i]=0,to[n+1][i]=n+1;
	For(i,1,n){
		ll pp=lst[(p[i]+d[i])%k];
		L[i]=pp;
		lst[(p[i]+d[i])%k]=i;
	}
	lst.clear();
	tot=0;
	Rof(i,n,1){
		ll pp=lst[((p[i]-d[i])%k+k)%k];
		if(!pp) R[i]=n+1;
		else R[i]=pp;
		c[++tot]=a[i]=((p[i]-d[i])%k+k)%k;
		lst[((p[i]-d[i])%k+k)%k]=i;
	}
	lst.clear();
	For(i,1,n) to[i][0]=R[L[i]];
	For(j,1,49){
		For(i,1,n){
			to[i][j]=to[to[i][j-1]][j-1];
		}
	}
	sort(c+1,c+tot+1);
	tot=unique(c+1,c+tot+1)-c-1;
	c[tot+1]=1e18;
	c[0]=-1e18;
	For(i,1,n) a[i]=lower_bound(c+1,c+tot+1,a[i])-c;
	For(i,1,tot) s[i].clear();
	For(i,1,n) s[a[i]].insert(p[i]);
	q=read();
	while(q--){
		ll x=read();
		//cout<<x<<endl;
		int now=lower_bound(c,c+tot+2,x%k)-c;
		if(c[now]!=x%k){
			printf("YES\n");
			continue;
		}
		auto it=s[now].lower_bound(x);
		if(it==s[now].end()){
			printf("YES\n");
			continue;
		}
		ll val=*it;
		//cout<<val<<endl;
		val=lower_bound(p+1,p+n+1,val)-p;
		Rof(i,49,0) val=to[val][i];
		if(val==0 || val==n+1) printf("YES\n");
		else printf("NO\n");
	}
}

int main()
{
	//freopen("game.in","r",stdin);
    //freopen("game.out","w",stdout);
    T=read();
    while(T--) sol();
	return 0;
}
/*

*/

题解：CF2118D2 Red Light, Green Light (Hard version)

文章操作

前言

Solution

相关推荐

评论

题解：CF2118D2 Red Light, Green Light (Hard version)