概要

各街灯が「暗くなる日」をあらかじめ求めておき、問い合わせの日数が小さい順に処理します。
暗くなった街灯を順に追加しながら、連続して暗い区間の長さを管理して答えを求めます。

考察

ある街灯が \(t\) 日後に暗いかどうかは、

\[ C_i(t) = \max(0, A_i - D_i \times t) \leq K \]

で判定できます。

ここで重要なのは、街灯の明るさは時間とともに減るだけなので、一度暗くなった街灯はその後ずっと暗いということです。

つまり、各街灯について「初めて暗くなる日」を求めておけば、問い合わせ \(T\) に対しては、

初めて暗くなる日が \(T\) 以下の街灯

だけを考えればよいです。

---

\(i\) 番目の街灯が初めて暗くなる日を \(t_i\) とします。

• もし \(A_i \leq K\) なら、最初から暗いので \(t_i = 0\)
• もし \(A_i > K\) かつ \(D_i = 0\) なら、明るさが下がらないので永遠に暗くならない
• それ以外の場合、

\[ A_i - D_i \times t \leq K \]

となる最小の整数 \(t\) を求めればよいので、

\[ t_i = \left\lceil \frac{A_i - K}{D_i} \right\rceil \]

です。

整数計算では、

\[ t_i = \frac{A_i - K + D_i - 1}{D_i} \]

で求められます。

---

次に、ある時点で暗い街灯の並びが分かったとします。

例えば、暗い街灯が連続して \(m\) 本ある区間では、その中から選べる部分区間の個数は

\[ \frac{m(m+1)}{2} \]

個です。

したがって、答えは

暗い街灯の連続区間ごとに \(\frac{m(m+1)}{2}\) を足したもの

になります。

---

素朴に各問い合わせごとに全街灯を調べると、\(O(NQ)\) かかります。
\(N+Q \leq 2 \times 10^5\) なので、これは間に合いません。

そこで、問い合わせを日数の昇順に並べて処理します。

日数が増えるにつれて、暗い街灯は増えるだけです。
そのため、まだ追加していない街灯のうち、暗くなる日が現在の問い合わせ日数以下のものを順に追加していけばよいです。

暗い街灯を追加したとき、左右にすでに暗い街灯があれば連結します。
この「連続区間の併合」は Union-Find を使うと効率よく管理できます。

アルゴリズム

1. 各街灯について、初めて暗くなる日 \(t_i\) を求める。
2. \((t_i, i)\) をイベントとして配列に入れる。
3. 問い合わせ \((T_j, j)\) を、元の番号付きで保存する。
4. イベントと問い合わせをそれぞれ日数の昇順にソートする。
5. Union-Find を用意する。
   • 各街灯が現在暗いかどうかを active で管理する。
   • 暗い街灯の連続区間を Union-Find の連結成分として管理する。
   • 現在の答えを total として持つ。
6. 問い合わせを日数の小さい順に処理する。
   • 暗くなる日が \(T_j\) 以下の街灯をすべて追加する。
   • 追加時に左右が暗ければ Union-Find で併合する。
   • その時点の total が答え。
7. 最後に、元の問い合わせ順に答えを出力する。

---

Union-Find で管理する値について説明します。

長さ \(x\) の暗い連続区間があるとき、その区間から選べる暗い部分区間の個数は

\[ f(x) = \frac{x(x+1)}{2} \]

です。

新しく暗い街灯を追加すると、まず長さ \(1\) の区間ができるので、答えに \(1\) を足します。

また、左右に暗い区間がある場合は併合します。

例えば、長さ \(a\) の区間と長さ \(b\) の区間を併合すると、長さ \(a+b\) の区間になります。

このとき答えは、

\[ -f(a) - f(b) + f(a+b) \]

だけ変化します。

コードでは、Union-Find の unite の中でこの更新を行っています。

計算量

• 時間計算量: \(O((N+Q)\log(N+Q))\)
  • 街灯イベントと問い合わせのソートにかかります。
  • Union-Find の操作はほぼ定数時間です。
• 空間計算量: \(O(N+Q)\)

実装のポイント

• 暗くなる日が存在しない街灯、つまり \(A_i > K\) かつ \(D_i = 0\) の場合は、十分大きい値 INF を設定します。

• 答えは最大で \(O(N^2)\) になるため、long long を使います。

• 問い合わせはソートして処理しますが、出力は元の順番で行う必要があるため、問い合わせの番号も一緒に保存します。

• Union-Find では、暗くなった街灯だけを active として扱い、左右の街灯が active のときだけ併合します。

  ソースコード

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

using ll = long long;

struct DSU {
    vector<int> parent, sz;
    vector<char> active;
    ll total = 0;

    DSU(int n) : parent(n), sz(n, 1), active(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    ll calc(ll x) {
        return x * (x + 1) / 2;
    }

    void unite(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return;

        if (sz[ra] < sz[rb]) swap(ra, rb);

        total -= calc(sz[ra]);
        total -= calc(sz[rb]);

        parent[rb] = ra;
        sz[ra] += sz[rb];

        total += calc(sz[ra]);
    }

    void add(int x) {
        if (active[x]) return;

        active[x] = 1;
        parent[x] = x;
        sz[x] = 1;
        total += 1;

        if (x > 0 && active[x - 1]) unite(x, x - 1);
        if (x + 1 < (int)active.size() && active[x + 1]) unite(x, x + 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    ll K;
    cin >> N >> Q >> K;

    const ll INF = (1LL << 60);

    vector<pair<ll, int>> events;

    for (int i = 0; i < N; i++) {
        ll A, D;
        cin >> A >> D;

        ll t;
        if (A <= K) {
            t = 0;
        } else if (D == 0) {
            t = INF;
        } else {
            t = (A - K + D - 1) / D;
        }

        events.push_back({t, i});
    }

    vector<pair<ll, int>> queries(Q);
    for (int i = 0; i < Q; i++) {
        ll T;
        cin >> T;
        queries[i] = {T, i};
    }

    sort(events.begin(), events.end());
    sort(queries.begin(), queries.end());

    DSU dsu(N);
    vector<ll> ans(Q);

    int idx = 0;
    for (auto [T, qi] : queries) {
        while (idx < N && events[idx].first <= T) {
            dsu.add(events[idx].second);
            idx++;
        }
        ans[qi] = dsu.total;
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。