K - 商店街の区画選び / Choosing Blocks in a Shopping Street Editorial by admin
gpt-5.5-xhigh概要
長さ \(K\) の連続区間を 1 つ選ぶとき、駐車スペース数が条件を満たす区間の中で、賃料合計の最小値を答える問題です。
賃料 \(A_i\) は更新されますが、駐車スペースの有無 \(C_i\) は変化しないため、長さ \(K\) の各区間に含まれる駐車スペース数は最初に計算して固定しておけます。
考察
長さ \(K\) の区間の開始位置を \(l\) とします。
区間 \([l, l+K-1]\) について、
- 賃料合計を \(S_l\)
- 駐車スペース数を \(P_l\)
とします。
このとき質問は、
\(P_l \geq X\) を満たす開始位置 \(l\) の中で、\(S_l\) の最小値を求める
という形になります。
長さ \(K\) の区間は全部で
\[ M = N - K + 1 \]
個あります。
素朴な方法
各質問ごとに全ての長さ \(K\) の区間を調べると \(O(N)\) かかります。
また、賃料変更で \(A_i\) が変わると、その区画を含む長さ \(K\) の区間すべての賃料合計が変わります。 最大で \(K\) 個の区間が影響を受けるため、毎回直接更新すると \(O(K)\) かかります。
制約は \(N \leq 10^5\), \(Q \leq 5 \times 10^4\) なので、単純に処理すると間に合いません。
重要な気づき
賃料変更によって変化するのは \(S_l\) だけです。
一方で、駐車スペース数 \(P_l\) は \(C_i\) が変化しないため、最初から最後まで固定です。
つまり、必要な処理は次の 2 種類です。
- 連続した範囲の \(S_l\) に同じ値を加算する
- \(P_l \geq X\) を満たす \(l\) の中で \(S_l\) の最小値を求める
これを平方分割で管理します。
アルゴリズム
1. 長さ \(K\) の各区間を前計算する
累積和を使って、各開始位置 \(l\) に対して
\[ S_l = A_l + A_{l+1} + \cdots + A_{l+K-1} \]
\[ P_l = C_l + C_{l+1} + \cdots + C_{l+K-1} \]
を計算します。
実装では 0-indexed で扱っているため、開始位置は \(0 \leq l < M\) です。
2. 賃料変更の影響範囲
区画 \(pos\) の賃料が \(\Delta\) だけ変化したとします。
この区画を含む長さ \(K\) の区間の開始位置 \(l\) は、
\[ l \leq pos \leq l+K-1 \]
を満たすものです。
これを変形すると、
\[ pos-K+1 \leq l \leq pos \]
です。
したがって、実際の範囲は
\[ \max(0, pos-K+1) \leq l \leq \min(pos, M-1) \]
となります。
この範囲の \(S_l\) すべてに \(\Delta\) を加算すればよいです。
3. 平方分割で管理する
開始位置 \(l\) をブロックに分けます。
各ブロックについて、次の情報を持ちます。
- そのブロックに含まれる開始位置
- 各開始位置の駐車スペース数 \(P_l\)
- \(P_l\) の昇順に並べた添字列
- その並びに対する suffix minimum
- ブロック全体に加算された遅延値
lazy
suffix minimum とは
ブロック内の開始位置を \(P_l\) の昇順に並べます。
例えば、あるブロック内で
| 並び順 | \(P_l\) | \(S_l\) |
|---|---|---|
| 0 | 1 | 100 |
| 1 | 2 | 80 |
| 2 | 3 | 120 |
| 3 | 5 | 70 |
となっているとします。
質問で \(X=3\) が来た場合、\(P_l \geq 3\) のものだけを見たいので、並び順 2 以降が対象です。
そこで、
\[ suff[i] = i 番目以降の S_l の最小値 \]
を持っておけば、二分探索で最初に \(P_l \geq X\) となる位置を探し、その位置の suff を見るだけで、そのブロック内の答えが分かります。
4. 範囲加算
\(S_l\) の範囲加算では、対象範囲が複数ブロックにまたがることがあります。
ブロック全体が範囲に含まれる場合
→lazyに加算するだけでよいです。ブロックの一部だけが範囲に含まれる場合
→ 対象の \(S_l\) を直接更新し、そのブロックの suffix minimum を作り直します。
駐車スペース数 \(P_l\) は変わらないため、並び順は作り直す必要がありません。
5. 質問処理
質問 \(X\) に対して、全ブロックを見ます。
各ブロックで、
- \(P_l \geq X\) となる最初の位置を二分探索で探す
- そこから後ろの \(S_l\) の最小値を
suffで取得する - ブロック全体の遅延値
lazyを足す
これを全ブロックについて行い、最小値を答えます。
条件を満たす区間が 1 つもなければ IMPOSSIBLE を出力します。
計算量
\(M = N-K+1\)、ブロックサイズを \(B\) とします。
- 初期化: \(O(M \log B)\)
- 賃料変更 1 回: \(O(B + M/B)\)
- 質問 1 回: \(O((M/B) \log B)\)
- 空間計算量: \(O(M)\)
この実装では \(B=512\) としており、\(M \leq 10^5\) なので十分高速に動作します。
実装のポイント
- 入力は 1-indexed ですが、実装では 0-indexed に直しています。
- 賃料変更時は、元の値との差分
$\( \Delta = Y - A_{pos} \)$
を求め、その差分だけ影響する区間に加算します。
駐車スペース数 \(P_l\) は更新されないため、各ブロック内で \(P_l\) 順に並べた配列は最初に作るだけでよいです。
ブロック全体への加算は
lazyに溜め、一部だけ更新した場合のみ suffix minimum を再構築します。ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL << 62);
struct SqrtDS {
static constexpr int BS = 512;
struct Block {
int l, r;
vector<int> idx;
vector<int> counts;
vector<ll> suff;
};
int n, nb;
vector<ll> val, lazy;
vector<int> cnt;
vector<Block> blocks;
SqrtDS(const vector<ll>& init, const vector<int>& c) {
n = (int)init.size();
val = init;
cnt = c;
nb = (n + BS - 1) / BS;
lazy.assign(nb, 0);
blocks.resize(nb);
for (int b = 0; b < nb; b++) {
int l = b * BS;
int r = min(n, l + BS);
blocks[b].l = l;
blocks[b].r = r;
int len = r - l;
blocks[b].idx.resize(len);
for (int i = 0; i < len; i++) blocks[b].idx[i] = l + i;
sort(blocks[b].idx.begin(), blocks[b].idx.end(), [&](int x, int y) {
if (cnt[x] != cnt[y]) return cnt[x] < cnt[y];
return x < y;
});
blocks[b].counts.resize(len);
for (int i = 0; i < len; i++) {
blocks[b].counts[i] = cnt[blocks[b].idx[i]];
}
blocks[b].suff.resize(len + 1);
rebuild(b);
}
}
void rebuild(int b) {
Block& bl = blocks[b];
int len = (int)bl.idx.size();
bl.suff[len] = INF;
for (int i = len - 1; i >= 0; i--) {
bl.suff[i] = min(bl.suff[i + 1], val[bl.idx[i]]);
}
}
void add_in_block(int b, int l, int r, ll d) {
if (l > r) return;
Block& bl = blocks[b];
if (l == bl.l && r == bl.r - 1) {
lazy[b] += d;
return;
}
for (int i = l; i <= r; i++) val[i] += d;
rebuild(b);
}
void range_add(int l, int r, ll d) {
if (l > r || d == 0) return;
int lb = l / BS;
int rb = r / BS;
if (lb == rb) {
add_in_block(lb, l, r, d);
} else {
add_in_block(lb, l, blocks[lb].r - 1, d);
add_in_block(rb, blocks[rb].l, r, d);
for (int b = lb + 1; b <= rb - 1; b++) {
lazy[b] += d;
}
}
}
ll query(int x) const {
ll ans = INF;
for (int b = 0; b < nb; b++) {
const Block& bl = blocks[b];
const vector<int>& co = bl.counts;
int len = (int)co.size();
if (x > co[len - 1]) continue;
int p = 0;
if (x > co[0]) {
int lo = 0, hi = len;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (co[mid] < x) lo = mid + 1;
else hi = mid;
}
p = lo;
}
ans = min(ans, bl.suff[p] + lazy[b]);
}
return ans;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K, Q;
cin >> N >> K >> Q;
vector<ll> 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];
vector<ll> prefA(N + 1, 0);
vector<int> prefC(N + 1, 0);
for (int i = 0; i < N; i++) {
prefA[i + 1] = prefA[i] + A[i];
prefC[i + 1] = prefC[i] + C[i];
}
int M = N - K + 1;
vector<ll> init(M);
vector<int> winC(M);
int maxC = 0;
for (int l = 0; l < M; l++) {
init[l] = prefA[l + K] - prefA[l];
winC[l] = prefC[l + K] - prefC[l];
maxC = max(maxC, winC[l]);
}
SqrtDS ds(init, winC);
string out;
out.reserve(Q * 24);
for (int qi = 0; qi < Q; qi++) {
int T;
ll X, Y;
cin >> T >> X >> Y;
if (T == 1) {
int pos = (int)X - 1;
ll delta = Y - A[pos];
A[pos] = Y;
if (delta != 0) {
int l = max(0, pos - K + 1);
int r = min(pos, M - 1);
ds.range_add(l, r, delta);
}
} else {
int need = (int)X;
if (need > maxC) {
out += "IMPOSSIBLE\n";
} else {
ll ans = ds.query(need);
if (ans >= INF / 2) out += "IMPOSSIBLE\n";
else {
out += to_string(ans);
out += '\n';
}
}
}
}
cout << out;
return 0;
}
この解説は gpt-5.5-xhigh によって生成されました。
posted:
last update: