K - 商店街の区画選び / Choosing Blocks in a Shopping Street Editorial by admin
gemini-3.5-flash-thinking概要
この問題は、商店街の連続する \(K\) 個の区画の選び方（全部で \(N - K + 1\) 通り）について、賃料の変更（区間加算）を反映しながら、「駐車スペースが \(X\) 個以上ある選び方のうち、賃料合計の最小値」を高速に求める問題です。
データの更新と条件付きの最小値検索を効率的に行うために、平方分割（Square Root Decomposition） を用いて解くことができます。
考察
1. 問題の定式化
連続する \(K\) 個の区画の選び方は、左端の区画を \(l\) \((0 \leq l \leq N-K)\) とすると、全部で \(M = N - K + 1\) 通りあります。 各選び方 \(l\) について、以下の 2 つの値を定義します。 - \(W_l\) : 左から \(l\) 番目から \(l+K-1\) 番目までの区画の賃料の合計 - \(S_l\) : 左から \(l\) 番目から \(l+K-1\) 番目までの区画のうち、駐車スペースがある区画の数
初期状態の \(W_l\) と \(S_l\) は、累積和やスライディングウィンドウ（尺取り法）を用いることで、全体で \(O(N)\) で計算できます。
2. クエリの性質
\(T = 1\)（賃料の変更） 左から \(X\) 番目の区画の賃料が \(Y\) に変更され、差分を \(d = Y - A_X\) とします。 この変更は、区画 \(X\) を含むすべての連続する \(K\) 個の区画の賃料合計に影響します。 具体的には、左端 \(l\) が \(\max(0, X - K + 1) \leq l \leq \min(M - 1, X)\) の範囲にあるすべての \(W_l\) に一律で \(d\) が加算されます。 これは、配列 \(W\) に対する 区間加算クエリ です。
\(T = 2\)（質問） \(S_l \ge X\) を満たす \(l\) のうち、\(W_l\) の最小値を求めます。 ここで重要なのは、駐車スペースの有無 \(C_i\) は変化しないため、\(S_l\) の値はクエリを通じて不変である という点です。一方で、\(W_l\) の値は \(T=1\) のクエリによって変化します。
3. なぜ単純な方法では間に合わないか？
- 質問クエリごとにすべての \(l\) を走査すると、1回あたり \(O(N)\) かかり、全体で \(O(QN)\) となって実行時間制限に間に合いません（TLE）。
- セグメント木などのデータ構造を使う場合、区間加算を行いながら「\(S_l \ge X\) である位置の最小値」を求めるのは、条件がインデックスではなく値（\(S_l\)）に基づいているため、単純な形では管理が困難です。
4. 平方分割によるアプローチ
\(S_l\) が固定されている点に着目し、要素数 \(M\) の配列をサイズ \(B \approx \sqrt{M}\) のブロックに分割する 平方分割 を適用します。
各ブロック内で、以下のような前計算テーブル val を用意します。
- val[s] : そのブロック内で \(S_l \geq s\) を満たす \(W_l\) の最小値
このテーブルをブロックごとに持っておけば、質問クエリに対して、各ブロックから \(O(1)\) で条件を満たす最小値を取得できます。
アルゴリズム
1. ブロックの管理と構築（build）
各ブロックについて、ブロック内の \(S_l\) の最小値 \(S_{\min}\) と最大値 \(S_{\max}\) を求めます。
そして、サイズ \(S_{\max} - S_{\min} + 1\) の配列 val を以下のように構築します。
valのすべての要素を無限大（\(\infty\)）で初期化します。- ブロック内の各要素 \(l\) について、
val[S_l - S_min] = min(val[S_l - S_min], W_l)と更新します。 - \(s\) を \(S_{\max} - 1\) から \(S_{\min}\) まで逆順に走査し、
val[s - S_min] = min(val[s - S_min], val[s + 1 - S_min])と累積最小値（後ろからの累積 min）を取ります。
これにより、val[s - S_min] には「ブロック内で \(S_l \geq s\) を満たす \(W_l\) の最小値」が格納されます。この構築にかかる時間はブロックのサイズ \(B\) に対して \(O(B)\) です。
2. 更新クエリ（\(T = 1\)）
区間 \([QL, QR]\) に値 \(d\) を加算します。
- 完全に含まれるブロック:
ブロック全体への加算値を表す変数 add に \(d\) を足すだけで、\(O(1)\) で処理します。
- 部分的に重なるブロック:
一度 add の値をブロック内の各要素の実値 W に反映（push）させた後、範囲内の要素に直接 \(d\) を加算します。その後、そのブロックの build 関数を呼び出してテーブルを再構築します。
1回あたりの更新に必要な計算量は、完全に含まれるブロックが \(O(M/B)\) 個、部分的に重なるブロックが最大 2 個（再構築に \(O(B)\)）なので、全体で \(O(M/B + B)\) となります。
3. 質問クエリ（\(T = 2\)）
条件 \(S_l \geq X\) を満たす最小値を求めます。 各ブロック \(b\) について、以下のように \(O(1)\) で候補を求め、その全体の最小値を取ります。
- \(X \leq S_{\min}\) の場合：ブロック内のすべての要素が条件を満たすため、ブロック全体の最小値
val[0] + addが候補となります。 - \(S_{\min} < X \leq S_{\max}\) の場合：
val[X - S_min] + addが候補となります。 - \(X > S_{\max}\) の場合：ブロック内に条件を満たす要素は存在しません。
すべてのブロックを走査するため、1回あたりの計算量は \(O(M/B)\) です。
計算量
\(B = \sqrt{M}\) と設定します。
時間計算量:
- 初期構築: \(O(N)\)
- 更新クエリ: \(O(\sqrt{N})\)
- 質問クエリ: \(O(\sqrt{N})\)
- 全体: \(O(N + Q \sqrt{N})\) 制約 \(N \leq 10^5, Q \leq 5 \times 10^4\) において、\(\sqrt{N} \approx 316\) であるため、総計算回数は約 \(1.5 \times 10^7\) 回となり、実行時間制限に余裕で間に合います。
空間計算量:
- 各ブロックの
val配列のサイズの合計は高々 \(O(N)\) です。 - 全体: \(O(N)\)
- 各ブロックの
実装のポイント
遅延評価（
push）のタイミング: 部分的に重なるブロックを更新する際は、必ず事前にaddの値を各要素のWに足し合わせてから個別の更新を行い、addを \(0\) にクリアしてください。これを怠ると、過去の一括加算分が消えてしまったり、二重に加算されたりする原因になります。インデックスのオフセット: \(S_l\) の値は \(0\) から \(K\) までの値を取り得ますが、ブロック内での実際の範囲は \([S_{\min}, S_{\max}]\) に収まります。メモリを節約し、探索を高速化するために、
val配列のインデックスを \(S_{\min}\) だけずらして（オフセットして）管理しています。インデックスの境界: \(T=1\) のクエリで更新する範囲 \([QL, QR]\) は、区画のインデックス \(X\) に対して \(QL = \max(0, X - K + 1)\)、\(QR = \min(M - 1, X)\) となります。境界をはみ出さないように
maxやminで制限することに注意してください。ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const long long INF = 1e18;
struct Block {
int L, R;
long long add;
vector<long long> W;
vector<int> S;
int S_min, S_max;
vector<long long> val;
void build() {
int sz = S_max - S_min + 1;
fill(val.begin(), val.end(), INF);
for (int i = 0; i <= R - L; ++i) {
int s = S[i];
val[s - S_min] = min(val[s - S_min], W[i]);
}
for (int s = S_max - 1; s >= S_min; --s) {
val[s - S_min] = min(val[s - S_min], val[s + 1 - S_min]);
}
}
void push() {
if (add != 0) {
for (auto& w : W) w += add;
add = 0;
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K, Q;
if (!(cin >> N >> K >> Q)) return 0;
vector<long long> A(N);
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
vector<int> C(N);
for (int i = 0; i < N; ++i) {
cin >> C[i];
}
int M = N - K + 1;
vector<long long> init_W(M, 0);
vector<int> init_S(M, 0);
long long cur_W = 0;
int cur_S = 0;
for (int i = 0; i < K; ++i) {
cur_W += A[i];
cur_S += C[i];
}
init_W[0] = cur_W;
init_S[0] = cur_S;
for (int l = 1; l < M; ++l) {
cur_W += A[l + K - 1] - A[l - 1];
cur_S += C[l + K - 1] - C[l - 1];
init_W[l] = cur_W;
init_S[l] = cur_S;
}
int B = max(1, (int)sqrt(M));
int D = (M + B - 1) / B;
vector<Block> blocks(D);
for (int b = 0; b < D; ++b) {
blocks[b].L = b * B;
blocks[b].R = min(M - 1, (b + 1) * B - 1);
blocks[b].add = 0;
int len = blocks[b].R - blocks[b].L + 1;
blocks[b].W.resize(len);
blocks[b].S.resize(len);
blocks[b].S_min = K + 1;
blocks[b].S_max = -1;
for (int i = 0; i < len; ++i) {
int l = blocks[b].L + i;
blocks[b].W[i] = init_W[l];
blocks[b].S[i] = init_S[l];
blocks[b].S_min = min(blocks[b].S_min, blocks[b].S[i]);
blocks[b].S_max = max(blocks[b].S_max, blocks[b].S[i]);
}
blocks[b].val.resize(blocks[b].S_max - blocks[b].S_min + 1);
blocks[b].build();
}
auto update = [&](int QL, int QR, long long d) {
for (int b = 0; b < D; ++b) {
if (blocks[b].R < QL || QR < blocks[b].L) {
continue;
}
if (QL <= blocks[b].L && blocks[b].R <= QR) {
blocks[b].add += d;
} else {
blocks[b].push();
int start = max(QL, blocks[b].L);
int end = min(QR, blocks[b].R);
for (int l = start; l <= end; ++l) {
blocks[b].W[l - blocks[b].L] += d;
}
blocks[b].build();
}
}
};
auto query = [&](int X) {
long long ans = INF;
for (int b = 0; b < D; ++b) {
if (X <= blocks[b].S_min) {
ans = min(ans, blocks[b].val[0] + blocks[b].add);
} else if (X <= blocks[b].S_max) {
ans = min(ans, blocks[b].val[X - blocks[b].S_min] + blocks[b].add);
}
}
return ans;
};
for (int q = 0; q < Q; ++q) {
int T;
cin >> T;
if (T == 1) {
int X;
long long Y;
cin >> X >> Y;
--X; // 0-indexed
long long old = A[X];
long long d = Y - old;
A[X] = Y;
int QL = max(0, X - K + 1);
int QR = min(M - 1, X);
update(QL, QR, d);
} else {
int X;
long long Y;
cin >> X >> Y; // Y is unused
long long ans = query(X);
if (ans >= INF) {
cout << "IMPOSSIBLE\n";
} else {
cout << ans << "\n";
}
}
}
return 0;
}
この解説は gemini-3.5-flash-thinking によって生成されました。
posted:
last update: