K - 商店街の区画選び / Choosing Blocks in a Shopping Street Editorial by admin
gpt-5.5-high概要
長さ \(K\) の連続区間をすべて「候補」として扱い、各候補について「賃料合計」と「駐車スペース数」を管理します。
賃料変更は候補列に対する区間加算、質問は「駐車スペース数が \(X\) 以上の候補の賃料合計の最小値」を求める問題に変換できます。
考察
長さ \(K\) の区間の左端を \(l\) とすると、候補は
[ [l, l+K-1] ]
です。
候補の数を
[ M = N-K+1 ]
とします。
各候補 \(l\) について、次を定義します。
- \(S_l\)：区間 \([l, l+K-1]\) の賃料合計
- \(P_l\)：区間 \([l, l+K-1]\) に含まれる駐車スペース数
質問では、条件
[ P_l \ge X ]
を満たす候補の中で、\(S_l\) の最小値を求めます。
ここで重要なのは、\(C_i\) は操作で変化しないため、各候補の \(P_l\) は最初から最後まで変わらないという点です。
一方、賃料 \(A_p\) が変更されたとき、影響を受けるのは「位置 \(p\) を含む長さ \(K\) の区間」だけです。
候補 \(l\) が位置 \(p\) を含む条件は
[ l \le p \le l+K-1 ]
なので、
[ p-K+1 \le l \le p ]
です。
候補の左端 \(l\) は \(0 \le l < M\) なので、実際に更新される範囲は
[ L = \max(0, p-K+1) ]
[ R = \min(p, M-1) ]
になります。
賃料の変更量を \(\Delta\) とすると、すべての \(l \in [L,R]\) について
[ S_l \leftarrow S_l + \Delta ]
となります。
したがって、問題は次のデータ構造問題に変換できます。
- 配列 \(S\) に対する区間加算
- 固定値 \(P_l\) について、\(P_l \ge X\) を満たす要素の \(S_l\) の最小値を求める
素朴に各質問で全候補を調べると \(O(M)\) かかり、最大で \(M=10^5, Q=5 \times 10^4\) なので間に合いません。
そこで平方分割を使います。
アルゴリズム
1. 初期状態の計算
まず、すべての長さ \(K\) の区間について、賃料合計 \(S_l\) と駐車スペース数 \(P_l\) を求めます。
これはスライド窓で計算できます。
最初の区間について
[ S_0 = A_0 + A1 + \cdots + A{K-1} ]
[ P_0 = C_0 + C1 + \cdots + C{K-1} ]
を求めます。
次の区間へ移るときは、左端から外れる要素を引き、右端に新しく入る要素を足します。
[ Sl = S{l-1} - A{l-1} + A{l+K-1} ]
[ Pl = P{l-1} - C{l-1} + C{l+K-1} ]
これにより全候補を \(O(N)\) で計算できます。
2. 平方分割で管理する
候補列 \(0,1,\dots,M-1\) をブロックに分けます。
各ブロックについて、次を持ちます。
- ブロックに含まれる候補の範囲
- ブロック全体に加算された遅延値
lazy - 候補を \(P_l\) の昇順に並べた順序
- その順序における \(P_l\) の配列
- その順序における \(S_l\) の suffix minimum
例えば、あるブロック内で \(P_l\) の昇順に並べたとき、
[ P = [1,2,4,4] ]
だったとします。
質問で \(X=3\) が来た場合、条件 \(P_l \ge 3\) を満たすのは後ろの
[ [4,4] ]
の部分です。
つまり、\(P_l\) で二分探索して最初に \(X\) 以上になる位置を見つければ、そこから後ろの \(S_l\) の最小値が答え候補になります。
そのために、各ブロックで suffix minimum を持ちます。
[ \text{suf}[i] = i \text{ 番目以降の } S_l \text{ の最小値} ]
を持っておけば、ブロック内の答えは \(O(\log B)\) で求められます。
ここで \(B\) はブロックサイズです。
3. 賃料変更クエリ
入力では \(1\)-indexed で位置 \(X\) が与えられるので、コードでは
[ p = X-1 ]
に直します。
古い賃料を \(A_p\)、新しい賃料を \(Y\) とすると、
[ \Delta = Y - A_p ]
です。
影響を受ける候補の左端は
[ L = \max(0, p-K+1) ]
[ R = \min(p, M-1) ]
なので、候補列 \(S\) の区間 \([L,R]\) に \(\Delta\) を加算します。
平方分割では、更新区間に対して次のように処理します。
- ブロック全体が更新範囲に含まれる場合
→lazyに \(\Delta\) を足すだけ - ブロックの一部だけが更新範囲に含まれる場合
→ 該当する \(S_l\) を直接更新し、そのブロックの suffix minimum を作り直す
\(P_l\) は変化しないため、並び順は作り直す必要がありません。
4. 質問クエリ
質問では、条件
[ P_l \ge X ]
を満たす候補の中で、\(S_l\) の最小値を求めます。
各ブロックについて、
- ブロック内の最大 \(P_l\) が \(X\) 未満なら、そのブロックには候補がないので無視
- \(P_l\) の昇順配列に対して二分探索し、最初に \(X\) 以上となる位置を探す
- そこから後ろの suffix minimum を見る
- ブロックの
lazyを足した値を答え候補にする
全ブロックについてこれを行い、最小値を答えます。
もし全体の最大駐車スペース数が \(X\) 未満なら、そもそも条件を満たす候補は存在しないので IMPOSSIBLE です。
5. ブロックサイズについて
理論的には、ブロックサイズを
[ B \approx \sqrt{M} ]
程度にすれば十分高速です。
コードではさらに高速化するため、全操作を先に読み込み、複数のブロックサイズ候補について処理コストを見積もり、最もよさそうなサイズを選んでいます。
これは実行時間を改善するための工夫であり、アルゴリズムの本質は平方分割です。
計算量
\(M=N-K+1\)、ブロックサイズを \(B\) とします。
- 初期計算: \(O(N)\)
- ブロック構築: \(O(M \log B)\)
- 賃料変更 1 回: \(O(B + M/B)\)
- 質問 1 回: \(O((M/B)\log B)\)
したがって、\(B \approx \sqrt{M}\) とすると、
- 時間計算量: \(O(N + M\log M + Q\sqrt{M}\log M)\)
- 空間計算量: \(O(N+Q)\)
データ構造部分だけなら空間計算量は \(O(M)\) です。
実装のポイント
- 賃料合計は最大で \(10^5 \times 10^9 = 10^{14}\) 程度になるため、
long longを使います。 - 入力は \(1\)-indexed ですが、実装では \(0\)-indexed に直して扱います。
- 賃料変更で影響を受ける候補の範囲は
[ [\max(0,p-K+1), \min(p,M-1)] ]
です。
- 各ブロックでは \(P_l\) の順序は変化しないため、更新時に並べ替え直す必要はありません。
- ブロック全体への加算は lazy に持ち、一部更新のときだけ実際の値を更新して suffix minimum を再構築します。
- 答えが存在しない場合を判定するため、全候補の最大 \(P_l\) を持っておくと便利です。
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL << 62);
struct Op {
int t, x;
ll y;
};
struct SqrtDecomp {
struct Block {
int l, r;
int minB, maxB;
ll lazy;
vector<int> ord;
vector<int> bvals;
vector<ll> suf;
};
int n, BS, nb;
int globalMax;
vector<ll> val;
vector<Block> blocks;
SqrtDecomp(const vector<ll>& initial, const vector<int>& park, int blockSize) {
n = (int)initial.size();
BS = max(1, min(blockSize, n));
nb = (n + BS - 1) / BS;
val = initial;
globalMax = *max_element(park.begin(), park.end());
blocks.resize(nb);
for (int b = 0; b < nb; b++) {
int l = b * BS;
int r = min(n, (b + 1) * BS);
int len = r - l;
blocks[b].l = l;
blocks[b].r = r;
blocks[b].lazy = 0;
blocks[b].ord.resize(len);
iota(blocks[b].ord.begin(), blocks[b].ord.end(), l);
sort(blocks[b].ord.begin(), blocks[b].ord.end(), [&](int a, int c) {
if (park[a] != park[c]) return park[a] < park[c];
return a < c;
});
blocks[b].bvals.resize(len);
for (int i = 0; i < len; i++) {
blocks[b].bvals[i] = park[blocks[b].ord[i]];
}
blocks[b].minB = blocks[b].bvals.front();
blocks[b].maxB = blocks[b].bvals.back();
blocks[b].suf.assign(len, INF);
rebuild(b);
}
}
void rebuild(int b) {
Block& blk = blocks[b];
ll mn = INF;
for (int i = (int)blk.ord.size() - 1; i >= 0; i--) {
mn = min(mn, val[blk.ord[i]]);
blk.suf[i] = mn;
}
}
void addRange(int l, int r, ll delta) {
if (l > r || delta == 0) return;
int bl = l / BS;
int br = r / BS;
if (bl == br) {
Block& blk = blocks[bl];
if (l == blk.l && r + 1 == blk.r) {
blk.lazy += delta;
} else {
for (int i = l; i <= r; i++) val[i] += delta;
rebuild(bl);
}
return;
}
Block& left = blocks[bl];
if (l == left.l) {
left.lazy += delta;
} else {
for (int i = l; i < left.r; i++) val[i] += delta;
rebuild(bl);
}
for (int b = bl + 1; b < br; b++) {
blocks[b].lazy += delta;
}
Block& right = blocks[br];
if (r + 1 == right.r) {
right.lazy += delta;
} else {
for (int i = right.l; i <= r; i++) val[i] += delta;
rebuild(br);
}
}
ll query(int x) {
if (x > globalMax) return INF;
ll ans = INF;
for (int b = 0; b < nb; b++) {
Block& blk = blocks[b];
if (x > blk.maxB) continue;
int pos;
if (x <= blk.minB) {
pos = 0;
} else {
const vector<int>& v = blk.bvals;
int lo = 0, hi = (int)v.size();
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (v[mid] < x) lo = mid + 1;
else hi = mid;
}
pos = lo;
}
if (pos < (int)blk.suf.size()) {
ans = min(ans, blk.suf[pos] + blk.lazy);
}
}
return ans;
}
};
int choose_block_size(int M, int K, const vector<Op>& ops, int maxB) {
vector<pair<int, int>> ranges;
ll qImp = 0, qZero = 0, qOther = 0;
for (const auto& op : ops) {
if (op.t == 1) {
int p = op.x - 1;
int L = max(0, p - K + 1);
int R = min(p, M - 1);
ranges.push_back({L, R});
} else {
if (op.x > maxB) qImp++;
else if (op.x <= 0) qZero++;
else qOther++;
}
}
vector<int> cands;
auto addCand = [&](int b) {
b = max(1, min(b, M));
cands.push_back(b);
};
for (int b = 16; b <= 512; b += 16) addCand(b);
for (int b = 544; b <= 2048; b += 32) addCand(b);
for (int b = 2112; b <= 8192; b += 128) addCand(b);
for (int b = 8704; b <= 32768; b += 512) addCand(b);
for (long long b = 65536; b < M; b *= 2) addCand((int)b);
addCand(450);
addCand((int)sqrt((double)M) + 1);
addCand(M);
sort(cands.begin(), cands.end());
cands.erase(unique(cands.begin(), cands.end()), cands.end());
double best = 1e100;
int bestB = cands[0];
for (int b : cands) {
int nb = (M + b - 1) / b;
double lg = 1.0 + log2((double)b + 1.0);
double cost = 0;
cost += (double)qImp;
cost += (double)qZero * nb;
cost += (double)qOther * nb * lg;
for (auto [L, R] : ranges) {
int bl = L / b;
int br = R / b;
if (bl == br) {
int st = bl * b;
int en = min(M, st + b);
int len = en - st;
if (L == st && R + 1 == en) cost += 1;
else cost += (R - L + 1) + len;
} else {
int leftSt = bl * b;
int leftEn = min(M, leftSt + b);
int leftLen = leftEn - leftSt;
if (L == leftSt) cost += 1;
else cost += (leftEn - L) + leftLen;
cost += max(0, br - bl - 1);
int rightSt = br * b;
int rightEn = min(M, rightSt + b);
int rightLen = rightEn - rightSt;
if (R + 1 == rightEn) cost += 1;
else cost += (R - rightSt + 1) + rightLen;
}
if (cost >= best) break;
}
if (cost < best) {
best = cost;
bestB = b;
}
}
return bestB;
}
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<Op> ops(Q);
int queryCount = 0;
for (int i = 0; i < Q; i++) {
cin >> ops[i].t >> ops[i].x >> ops[i].y;
if (ops[i].t == 2) queryCount++;
}
int M = N - K + 1;
vector<ll> sums(M);
vector<int> park(M);
ll curSum = 0;
int curPark = 0;
for (int i = 0; i < K; i++) {
curSum += A[i];
curPark += C[i];
}
sums[0] = curSum;
park[0] = curPark;
for (int l = 1; l < M; l++) {
curSum += A[l + K - 1] - A[l - 1];
curPark += C[l + K - 1] - C[l - 1];
sums[l] = curSum;
park[l] = curPark;
}
int maxPark = *max_element(park.begin(), park.end());
int BS = choose_block_size(M, K, ops, maxPark);
SqrtDecomp ds(sums, park, BS);
string output;
output.reserve(queryCount * 16);
for (const auto& op : ops) {
if (op.t == 1) {
int p = op.x - 1;
ll newVal = op.y;
ll delta = newVal - A[p];
A[p] = newVal;
if (delta != 0) {
int L = max(0, p - K + 1);
int R = min(p, M - 1);
ds.addRange(L, R, delta);
}
} else {
ll ans = ds.query(op.x);
if (ans >= INF / 2) {
output += "IMPOSSIBLE\n";
} else {
output += to_string(ans);
output += '\n';
}
}
}
cout << output;
return 0;
}
この解説は gpt-5.5-high によって生成されました。
posted:
last update: