题解：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} 为一次跳跃，此时直接倍增跳足够多次就可以判断是否在环内。

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

#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;
}
/*

*/