各街頭が暗くなる日付を事前に求めておき、クエリも日付順に並べることで、問題は次のように変換できます。

問題： \(N\) 本の街頭がある。最初、全ての街頭は明るい。以下の \(2\) 種類のクエリが計 \(N+Q\) 個与えられるので順に処理せよ。

• 街頭 \(i\) が暗くなる
• 暗い部分区間の個数を求める

この問題を高速に解くためには、街頭 \(i\) が暗くなったときに、暗い部分区間の個数がどう変化するかが分かれば十分です。

街頭 \(i\) が暗くなるときの処理を以下のように行うことにします。

1. 街頭 \(i\) が暗くなる
2. 街頭 \(i-1\) が暗いならば、街頭 \(i\) を含む暗い街頭区間と街頭 \(i-1\) を含む暗い街頭区間をマージする
3. 街頭 \(i+1\) が暗いならば、街頭 \(i\) を含む暗い街頭区間と街頭 \(i+1\) を含む暗い街頭区間をマージする

2 つの暗い街頭区間をマージすると、その長さを \(x,y\) として、暗い部分区間の個数は \(xy\) 増えます。各街頭を含む暗い該当区間の長さを求めることは、DSU を用いることでクエリあたり \(O(\alpha(N))\) で行えるので、全体で \(O((N+Q)\log(N+Q))\) でこの問題を解くことができました。

実装上は \(N\) 本の街頭の両端に番兵として暗くならない街頭を用意するとよいです。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/dsu>
using namespace std;

int main(){
  int n, q, k;
  cin >> n >> q >> k;
  vector<array<int,3>> event;
  for(int i=0; i<n; i++){
    int a, d;
    cin >> a >> d;
    if(d > 0){
      event.push_back({(a-k+d-1)/d, 1, i+1});
    }else if(a <= k){
      event.push_back({0, 1, i+1});
    }
  }
  for(int i=0; i<q; i++){
    int t;
    cin >> t;
    event.push_back({t, 2, i});
  }
  sort(event.begin(), event.end());

  atcoder::dsu d(n+2);
  vector<long long> ans(q);
  vector<bool> ok(n+2, false);
  long long crr = 0;
  for(auto[t, f, i]: event){
    if(f == 1){
      ok[i] = true;
      crr++;
      for(int adj=i-1; adj<=i+1; adj+=2){
        if(ok[adj]){
          int x = d.size(i);
          int y = d.size(adj);
          crr += (long long)x * y;
          d.merge(i, adj);
        }
      }
    }else{
      ans[i] = crr;
    }
  }

  for(int i=0; i<q; i++){
    cout << ans[i] << endl;
  }
}

実装例 (Python)

from atcoder.dsu import DSU

N, Q, K = map(int, input().split())
event = []
for i in range(N):
  A, D = map(int, input().split())
  if D > 0:
    event.append(((A-K+D-1)//D, 1, i+1))
  elif A <= K:
    event.append((0, 1, i+1))
for i in range(Q):
  T = int(input())
  event.append((T, 2, i))
event.sort()

d = DSU(N+2)
ans = [0]*Q
ok = [False]*(N+2)
crr = 0
for t, f, i in event:
  if f == 1:
    ok[i] = True
    crr += 1
    for adj in [i-1, i+1]:
      if ok[adj]:
        x = d.size(i)
        y = d.size(adj)
        crr += x * y
        d.merge(i, adj)
  else:
    ans[i] = crr

print(*ans, sep="\n")