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

· · 题解

思路

简单清新思维题。

不难发现从 a_i 出发要么直接走出范围，要么碰上至少一个亮灯导致转向。于是考虑处理出“在第 i 个信号灯亮时位于 p_i，下一步向左/向右，能否在有限时间内走出范围”。

那么，我们考虑求从一个正亮的灯出发（等价于在此灯处转向），它会到达的下一个亮灯是哪一个，或它可以直接走出范围。对于从灯 i 亮时开始，从灯 i 走到灯 j(i<j)，在什么情况下到达灯 j 时它是亮的？显然相位差，即 d_j-d_i，要和到达两个点的时差，p_j-p_i，模 k 同余，有

p_j-p_i\equiv d_j-d_i\pmod k\\ p_i-d_i\equiv p_j-d_j\pmod k

所以，从灯 i 在其亮时出发向右走，碰到的第一个红灯是最小的 j>i 满足 d_i-p_i\equiv d_j-p_j\pmod k。要得到这个 j，我们考虑从灯 n 开始递减处理，开一个 map 桶，mp_x 存已经处理到的最小的 j 满足 d_j-p_j\equiv x\pmod k。

当 i>j 时，即向左走，有

p_i-p_j\equiv d_j-d_i\pmod k\\ p_i+d_i\equiv p_j+d_j\pmod k

同样开 map 桶处理即可。上述步骤时间复杂度 O(n\log n)。至此，我们得到了在每个灯处转向，面向左/右，下一个会到达的灯。

每个灯拆成两个点区分方向，建一个点表示走出边界，向下一个可以到达的灯连边，我们要得知它是否可以走到那个走出边界的点——那我们不妨建个反图，找出边界点可以到达的所有的点，只需要一次 DFS 就够了。

至此，我们得到了在每个灯处转向，面向左/右，能否在有限时间内走出边界。

接下来我们只需要对每个询问，找出它会到达的第一个亮的灯，就可以回答询问了。从 a 出发向右走到达亮灯 i(p_i>a) 当且仅当

p_i-a\equiv d_i\pmod k\\ a\equiv p_i-d_i\pmod k

这和处理“每个灯向右到达的第一个灯”时的式子类似，同样对 a 排序，从右往左处理即可。不用对 a 排序的方法是离散化所有 (p_i-d_i) 后对每一个 (p_i-d_i) 开一个 set，在对应的 set 里面二分最小的 i\ge a。

时间复杂度 O(\sum n\log n)。

代码

#include<bits/stdc++.h>
#define gc getchar
#define eb emplace_back
#define ef emplace_front
#define ep emplace
#ifndef DEBUG
#define debug
#endif
using namespace std;
template<typename T>void read(T &x){x = 0;int f = 1;char c = gc();while(!isdigit(c)){if(c == '-') f = -1;c = gc();}while(isdigit(c)) x = (x << 3) + (x << 1) + c - '0',c = gc();x *= f;}
const int N = 500000;
int T,n,q,nxt[N][2],it;
long long k,p[N],d[N];
bool esc[N],ans[N];
pair<long long,int> a[N];
map<long long,int>mp;
vector<int>e[N];
inline int plus(long long a,long long b){return (a + b) % k;}//(a+b)%k
inline int minus(long long a,long long b){return ((a - b) % k + k) % k;}//(a-b)%k
void sch(int u){
  esc[u] = true;
  for(auto v : e[u]) if(!esc[v]) sch(v);
}
int main(){
  cin.tie(0)->sync_with_stdio(0);
  read(T);
  while(T --){
    mp.clear();
    read(n),read(k);
    for(int i = 0;i <= 2 * n;i ++) e[i].clear(),esc[i] = false;
    for(int i = 1;i <= n;i ++) read(p[i]);
    for(int i = 1;i <= n;i ++) read(d[i]);
    //0 表示边界；1~n 表示每个亮灯开始向左走；n+1~2n 表示每个亮灯开始向右走
    for(int i = 1;i <= n;i ++){
      nxt[i][0] = mp[plus(p[i],d[i])];//从这个亮灯开始向左走可以到达的最近的亮灯，0 为边界
      mp[plus(p[i],d[i])] = i;
      e[nxt[i][0] ? nxt[i][0] + n : 0].eb(i);
      //从到达的最近的亮灯向 i 连边，因为 i 向左走到达的状态是 nxt 向右走，所以点的编号是 nxt+n
    }
    mp.clear();
    for(int i = n;i;i --){
      nxt[i][1] = mp[minus(p[i],d[i])];//同上
      mp[minus(p[i],d[i])] = i;
      e[nxt[i][1]].eb(i + n);
    }
    sch(0);//找出所有 0（边界）可达的点，标记 esc 表示可以走出边界
    read(q);
    for(int i = 1;i <= q;i ++) read(a[i].first),a[i].second = i;
    sort(a + 1,a + q + 1,[](pair<long long,int> a,pair<long long,int> b){
      return a.first > b.first;
    });//给询问排序从右往左处理
    mp.clear(),it = n;
    for(int i = 1;i <= q;i ++){
      auto [x,w] = a[i];
      while(it && p[it] >= x) mp[minus(p[it],d[it])] = it,it --;
      //保证 map 里面存的是所有 p[it]>=a[i] 的灯，用一个指针记录加入到了哪个灯
      ans[w] = esc[mp[x % k]];
    }
    for(int i = 1;i <= q;i ++){
      if(ans[i]) printf("YES\n");
      else printf("NO\n");
    }
  }
  return 0;
}