D - 街灯の暗い区間 / Dark Intervals of Street Lights Editorial by admin
Claude 4.6 Opus (Thinking)概要
各街灯が「暗く」なる時刻を求め、クエリを時刻の昇順にオフライン処理しながら、Union-Find で隣接する暗い街灯の連続区間を管理して部分区間の個数を効率的に数える問題です。
考察
重要な気づき①：各街灯が暗くなる時刻は一意に決まる
街灯 \(i\) の明るさ \(C_i(t) = \max(0, A_i - D_i \times t)\) は時間に対して単調に減少（非増加）します。よって、ある時刻 \(t_i\) を境に、\(t \geq t_i\) ならば常に暗い街灯になります。この 閾値時刻 \(t_i\) は次のように求まります：
- \(A_i \leq K\) の場合：最初から暗い → \(t_i = 0\)
- \(D_i = 0\) かつ \(A_i > K\) の場合：永遠に暗くならない → \(t_i = \infty\)
- それ以外：\(t_i = \lceil (A_i - K) / D_i \rceil\)
重要な気づき②：連続する暗い区間の長さから答えが求まる
暗い街灯の連続区間の長さが \(m\) のとき、その区間に含まれる部分区間 \((l, r)\) の個数は \(\frac{m(m+1)}{2}\) です。全体の答えは、すべての極大連続暗区間についてこの値を合計したものです。
素朴なアプローチの問題点
各クエリごとに全街灯を走査して暗い区間を数えると \(O(NQ)\) で、\(N + Q \leq 2 \times 10^5\) でも最悪 \(O(10^{10})\) 程度になり TLE です。
解決策：オフライン処理 + Union-Find
時刻が進むと暗い街灯が増えるだけ（減らない）という単調性を利用します。クエリを時刻の昇順にソートし、閾値時刻が小さい街灯から順に「暗い」状態に追加していきます。新たに暗くなった街灯を隣接する既に暗い街灯と Union-Find でマージすることで、連続区間の長さを効率的に管理できます。
アルゴリズム
- 閾値時刻の計算：各街灯 \(i\) について閾値時刻 \(t_i\) を求める。
- ソート：街灯を \(t_i\) の昇順に、クエリを \(T_j\) の昇順にそれぞれソートする。
- 逐次追加：クエリを小さい方から処理する。現在のクエリ時刻 \(T_j\) 以下の閾値を持つ街灯をすべて「有効化」する。
- Union-Find によるマージ：街灯 \(i\) を有効化したとき、左隣 \(i-1\) や右隣 \(i+1\) が既に有効なら Union-Find でマージする。マージ前後の \(\frac{m(m+1)}{2}\) の差分を
totalに加算する。 - 回答の記録：すべての追加が終わった時点の
totalがそのクエリの答え。
具体例：\(N=5\) で街灯の閾値時刻が \([0, 3, 1, 3, 2]\) のとき
| 時刻 | 新たに暗くなる街灯 | 暗い街灯列（●=暗） | 連続区間 | 部分区間数 |
|---|---|---|---|---|
| 0 | 1番 | ●○○○○ | [1] | 1 |
| 1 | 3番 | ●○●○○ | [1],[1] | 2 |
| 2 | 5番 | ●○●○● | [1],[1],[1] | 3 |
| 3 | 2,4番 | ●●●●● | [5] | 15 |
街灯2を追加 → 街灯1,3とマージして長さ3の区間。街灯4を追加 → 街灯3(の属する区間)と街灯5とマージして長さ5の区間。
計算量
- 時間計算量: \(O(N \log N + Q \log Q + N \alpha(N))\)
- ソートが支配的。\(\alpha(N)\) は逆アッカーマン関数（Union-Find の操作あたりのならし計算量）。
- 空間計算量: \(O(N + Q)\)
実装のポイント
閾値時刻が \(\infty\) の場合：\(D_i = 0\) かつ \(A_i > K\) の街灯は永遠に暗くならないので、十分大きい値（\(2 \times 10^9 + 1\) など、\(T_j\) の最大値を超える値）を設定する。
Union-Find のサイズ管理：
szを初期値 \(0\) にしておき、有効化時に \(1\) にセットする。これによりマージ時にサイズを正しく計算できる。差分更新：マージ時に「古い区間の部分区間数の合計」を引き、「新しい区間の部分区間数」を足すことで、全体の
totalを \(O(1)\) で更新する。天井除算：\((A_i - K + D_i - 1) / D_i\) で切り上げ除算を実現する。
ソースコード
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
vector<int> parent;
vector<long long> sz;
UnionFind(int n) : parent(n), sz(n, 0) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
while (parent[x] != x) x = parent[x] = parent[parent[x]];
return x;
}
void merge(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
parent[y] = x;
sz[x] += sz[y];
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
long long K;
cin >> N >> Q >> K;
vector<long long> threshold(N);
for (int i = 0; i < N; i++) {
long long A, D;
cin >> A >> D;
if (A <= K) {
threshold[i] = 0;
} else if (D == 0) {
threshold[i] = 2000000001LL; // infinity
} else {
threshold[i] = (A - K + D - 1) / D;
}
}
vector<int> order(N);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
return threshold[a] < threshold[b];
});
vector<pair<long long, int>> queries(Q);
for (int j = 0; j < Q; j++) {
cin >> queries[j].first;
queries[j].second = j;
}
sort(queries.begin(), queries.end());
auto countPairs = [](long long m) -> long long {
return m * (m + 1) / 2;
};
vector<long long> ans(Q);
UnionFind uf(N);
vector<bool> active(N, false);
long long total = 0;
int ptr = 0;
for (auto& [T, idx] : queries) {
while (ptr < N && threshold[order[ptr]] <= T) {
int i = order[ptr];
active[i] = true;
uf.sz[i] = 1;
long long oldCount = 0;
long long newSize = 1;
if (i > 0 && active[i - 1]) {
int root = uf.find(i - 1);
oldCount += countPairs(uf.sz[root]);
newSize += uf.sz[root];
uf.merge(i, i - 1);
}
if (i < N - 1 && active[i + 1]) {
int root = uf.find(i + 1);
oldCount += countPairs(uf.sz[root]);
newSize += uf.sz[root];
uf.merge(i, i + 1);
}
total += countPairs(newSize) - oldCount;
ptr++;
}
ans[idx] = total;
}
for (int j = 0; j < Q; j++) {
cout << ans[j] << '\n';
}
return 0;
}
この解説は claude4.6opus-thinking によって生成されました。