概要

\(N\) 本の街灯があり、時間経過とともに暗くなっていきます。各クエリで与えられる時刻 \(T_j\) において、「連続する区間がすべて暗い」という条件を満たす組 \((l, r)\) の総数を求める問題です。

考察

1. 暗い区間の数え上げ

連続する \(m\) 本の街灯がすべて「暗い」とき、その中から選べる部分区間 \((l, r)\) の個数は \(\frac{m(m+1)}{2}\) 個となります。 街灯全体の中に、極大な（それ以上延ばせない）暗い連続区間がいくつかある場合、全体の答えは各区間の長さ \(m_k\) に対して \(\sum \frac{m_k(m_k+1)}{2}\) となります。

2. 状態の変化と単調性

街灯 \(i\) が \(t\) 日後に暗い条件は \(A_i - D_i \times t \le K\) です。この式を変形すると、街灯 \(i\) が暗くなる最小の日数 \(S_i\) は以下のようになります。 - \(A_i \le K\) のとき：最初から暗い（\(S_i = 0\)） - \(A_i > K\) かつ \(D_i > 0\) のとき：\(t \ge \frac{A_i - K}{D_i}\) なので、 \(S_i = \lceil \frac{A_i - K}{D_i} \rceil\) - \(A_i > K\) かつ \(D_i = 0\) のとき：一生暗くならない（\(S_i = \infty\)）

一度暗くなった街灯は、その後ずっと暗いままです。つまり、「暗い街灯」は時間とともに増える一方であり、減ることはありません。

3. クエリのオフライン処理

クエリが与えられるたびに全街灯をチェックすると \(O(NQ)\) かかり、間に合いません。 しかし、街灯が暗くなるタイミング \(S_i\) と、クエリの時刻 \(T_j\) をあらかじめソートしておくことで、時刻の早い順に「新しく暗くなった街灯」を集合に追加していくオフライン処理が可能になります。

アルゴリズム

1. 準備:

   • 各街灯が暗くなる時刻 \(S_i\) を計算します。
   • 街灯を \(S_i\) の昇順にソートします。
   • クエリを \(T_j\) の昇順にソートします（元の順番を記録しておく必要があります）。

2. データ構造の利用:

   • 素集合データ構造（Union-Find / DSU）を用いて、隣接する暗い街灯同士を連結して管理します。
   • 各連結成分のサイズ（街灯の本数） \(m\) を保持します。

3. クエリ処理:

   • 現在の時刻 \(T_j\) までに新しく暗くなった街灯を順次処理します。
   • 街灯 \(i\) が暗くなったとき：
     • 最初、長さ \(1\) の区間ができるので、暫定の合計値に \(\frac{1(1+1)}{2} = 1\) を加算します。
     • 隣（\(i-1\) や \(i+1\)）がすでに暗い場合、それらの成分と結合します。
     • 結合する際、合計値から「結合前の各成分の計算値 \(\frac{m(m+1)}{2}\)」を引き、「結合後の新しい成分の計算値」を足すことで、差分更新を行います。

4. 出力:

   • 全てのクエリを処理した後、元のクエリ順に結果を出力します。

計算量

• 時間計算量: \(O((N + Q) \log (N + Q))\)
  • \(S_i\) の計算に \(O(N)\)
  • 街灯とクエリのソートに \(O(N \log N + Q \log Q)\)
  • Union-Find による処理に \(O((N + Q) \alpha(N))\) （\(\alpha\) はアッカーマン関数の逆関数）
• 空間計算量: \(O(N + Q)\)
  • 街灯情報、クエリ情報、Union-Find の配列などを保持するため。

実装のポイント

• 切り上げ除算: \(S_i = \lceil \frac{A_i - K}{D_i} \rceil\) は、整数演算では (A_i - K + D_i - 1) / D_i と書くことができます。

• 大きな値: \(D_i = 0\) で暗くならない場合は、クエリの最大値（\(10^9\)）より十分大きい値を \(S_i\) に設定します。

• 差分更新: 連結成分をマージする際、毎回すべての合計を計算し直すのではなく、変化があった部分だけを足し引きすることで効率的に計算できます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

/**
 * Problem: Dark Streetlight Intervals
 * We are given N streetlights, each with an initial brightness A_i and a decay rate D_i.
 * A light is "dark" if its brightness C_i(t) = max(0, A_i - D_i * t) is <= K.
 * For each query T_j, we need to count the number of pairs (l, r) such that all
 * streetlights from l to r are dark at time T_j.
 *
 * Solution Approach:
 * 1. For each light, calculate the earliest time S_i at which it becomes dark.
 *    - If A_i <= K, S_i = 0.
 *    - If A_i > K and D_i > 0, S_i = ceil((A_i - K) / D_i).
 *    - If A_i > K and D_i = 0, the light never becomes dark (S_i = infinity).
 * 2. Sort the lights by their activation time S_i and the queries by their time T_j.
 * 3. Use a Disjoint Set Union (DSU) to maintain continuous segments of dark lights.
 * 4. As time progresses (iterating through sorted queries), activate lights that have
 *    become dark and update the total count of dark sub-intervals.
 *    A segment of length m contributes m*(m+1)/2 sub-intervals.
 */

typedef long long ll;

// Disjoint Set Union (DSU) to maintain connected components of dark streetlights.
struct DSU {
    vector<int> parent;
    vector<ll> sz;
    DSU(int n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
        sz.assign(n + 1, 0);
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            // Union by size for efficiency
            if (sz[root_i] < sz[root_j]) swap(root_i, root_j);
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
        }
    }
};

// Function to calculate the number of pairs (l, r) in a segment of length m.
inline ll f(ll m) {
    return m * (m + 1) / 2;
}

struct Light {
    int id;
    ll s;
};

struct Query {
    int id;
    ll t;
};

int main() {
    // Fast I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    ll K;
    if (!(cin >> N >> Q >> K)) return 0;

    // Calculate activation time for each streetlight
    vector<Light> lights(N);
    for (int i = 0; i < N; ++i) {
        ll a, d;
        cin >> a >> d;
        ll s;
        if (a <= K) {
            s = 0;
        } else if (d == 0) {
            // Light never becomes dark if it starts bright and doesn't decay
            s = 2000000007LL; 
        } else {
            // Activation time is ceil((A_i - K) / D_i)
            s = (a - K + d - 1) / d;
        }
        lights[i] = {i + 1, s};
    }

    // Store queries and their original indices
    vector<Query> queries(Q);
    for (int i = 0; i < Q; ++i) {
        queries[i].id = i;
        cin >> queries[i].t;
    }

    // Sort lights and queries by time
    sort(lights.begin(), lights.end(), [](const Light& a, const Light& b) {
        if (a.s != b.s) return a.s < b.s;
        return a.id < b.id;
    });
    sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.t < b.t;
    });

    DSU dsu(N);
    vector<bool> is_dark(N + 2, false); // Padding to avoid boundary checks
    vector<ll> results(Q);
    ll total_count = 0;
    int light_idx = 0;

    // Process queries in chronological order
    for (int i = 0; i < Q; ++i) {
        while (light_idx < N && lights[light_idx].s <= queries[i].t) {
            int curr = lights[light_idx].id;
            if (!is_dark[curr]) {
                is_dark[curr] = true;
                dsu.sz[curr] = 1;
                total_count += f(1);

                // Merge with left neighbor if it is already dark
                if (curr > 1 && is_dark[curr - 1]) {
                    int root_left = dsu.find(curr - 1);
                    int root_curr = dsu.find(curr);
                    total_count -= f(dsu.sz[root_left]);
                    total_count -= f(dsu.sz[root_curr]);
                    dsu.unite(root_left, root_curr);
                    total_count += f(dsu.sz[dsu.find(curr)]);
                }
                // Merge with right neighbor if it is already dark
                if (curr < N && is_dark[curr + 1]) {
                    int root_right = dsu.find(curr + 1);
                    int root_curr = dsu.find(curr);
                    total_count -= f(dsu.sz[root_right]);
                    total_count -= f(dsu.sz[root_curr]);
                    dsu.unite(root_right, root_curr);
                    total_count += f(dsu.sz[dsu.find(curr)]);
                }
            }
            light_idx++;
        }
        results[queries[i].id] = total_count;
    }

    // Print results for each query in original order
    for (int i = 0; i < Q; ++i) {
        cout << results[i] << "\n";
    }

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。