K - 商店街の区画選び / Choosing Blocks in a Shopping Street Editorial by admin
gpt-5.5-highOverview
We treat all contiguous intervals of length \(K\) as “candidates” and maintain the “total rent” and “number of parking spaces” for each candidate.
Rent changes can be converted to range additions on the candidate array, and queries can be converted to finding the “minimum total rent among candidates with at least \(X\) parking spaces.”
Analysis
If the left endpoint of a length-\(K\) interval is \(l\), then the candidate is
[ [l, l+K-1] ]
Let the number of candidates be
[ M = N-K+1 ]
For each candidate \(l\), we define:
- \(S_l\): total rent of the interval \([l, l+K-1]\)
- \(P_l\): number of parking spaces in the interval \([l, l+K-1]\)
For queries, we find the minimum value of \(S_l\) among candidates satisfying the condition
[ P_l \ge X ]
The key observation here is that since \(C_i\) does not change through operations, \(P_l\) for each candidate remains constant from start to finish.
On the other hand, when rent \(A_p\) is changed, only “length-\(K\) intervals containing position \(p\)” are affected.
The condition for candidate \(l\) to contain position \(p\) is
[ l \le p \le l+K-1 ]
so
[ p-K+1 \le l \le p ]
Since the left endpoint \(l\) of a candidate satisfies \(0 \le l < M\), the actual range that gets updated is
[ L = \max(0, p-K+1) ]
[ R = \min(p, M-1) ]
If the change in rent is \(\Delta\), then for all \(l \in [L,R]\):
[ S_l \leftarrow S_l + \Delta ]
Therefore, the problem can be converted to the following data structure problem:
- Range addition on array \(S\)
- For fixed values \(P_l\), find the minimum \(S_l\) among elements where \(P_l \ge X\)
Naively checking all candidates for each query takes \(O(M)\), and with at most \(M=10^5, Q=5 \times 10^4\), this is too slow.
We use square root decomposition to solve this.
Algorithm
1. Computing the Initial State
First, we compute the total rent \(S_l\) and number of parking spaces \(P_l\) for all length-\(K\) intervals.
This can be computed using a sliding window.
For the first interval:
[ S_0 = A_0 + A1 + \cdots + A{K-1} ]
[ P_0 = C_0 + C1 + \cdots + C{K-1} ]
When moving to the next interval, we subtract the element leaving from the left and add the new element entering from the right:
[ Sl = S{l-1} - A{l-1} + A{l+K-1} ]
[ Pl = P{l-1} - C{l-1} + C{l+K-1} ]
This allows us to compute all candidates in \(O(N)\).
2. Managing with Square Root Decomposition
We divide the candidate array \(0,1,\dots,M-1\) into blocks.
For each block, we maintain:
- The range of candidates in the block
- A lazy value
lazyrepresenting the addition applied to the entire block - The order of candidates sorted by \(P_l\) in ascending order
- The array of \(P_l\) values in that order
- The suffix minimum of \(S_l\) in that order
For example, suppose within a block, the \(P_l\) values sorted in ascending order are:
[ P = [1,2,4,4] ]
If a query with \(X=3\) comes, the candidates satisfying \(P_l \ge 3\) are the latter part:
[ [4,4] ]
In other words, if we binary search on \(P_l\) to find the first position that is at least \(X\), then the minimum of \(S_l\) from that position onward becomes the answer candidate.
For this purpose, we maintain the suffix minimum for each block:
[ \text{suf}[i] = \text{minimum of } S_l \text{ from position } i \text{ onward} ]
With this, the answer within a block can be found in \(O(\log B)\).
Here \(B\) is the block size.
3. Rent Change Query
In the input, position \(X\) is given as \(1\)-indexed, so in the code we convert it to:
[ p = X-1 ]
If the old rent is \(A_p\) and the new rent is \(Y\), then:
[ \Delta = Y - A_p ]
The left endpoints of affected candidates are:
[ L = \max(0, p-K+1) ]
[ R = \min(p, M-1) ]
So we add \(\Delta\) to the range \([L,R]\) of the candidate array \(S\).
In square root decomposition, we handle the update range as follows:
- If the entire block is contained within the update range
→ Just add \(\Delta\) tolazy - If only part of the block is within the update range
→ Directly update the relevant \(S_l\) values and rebuild the suffix minimum for that block
Since \(P_l\) does not change, the sorted order does not need to be rebuilt.
4. Query
For a query, we find the minimum \(S_l\) among candidates satisfying:
[ P_l \ge X ]
For each block:
- If the maximum \(P_l\) in the block is less than \(X\), there are no valid candidates in this block, so skip it
- Binary search on the ascending \(P_l\) array to find the first position that is at least \(X\)
- Look at the suffix minimum from that position onward
- Add the block’s
lazyto the value and consider it as an answer candidate
We do this for all blocks and output the minimum.
If the maximum parking space count across all candidates is less than \(X\), then no candidate satisfies the condition, so the answer is IMPOSSIBLE.
5. Block Size
Theoretically, setting the block size to
[ B \approx \sqrt{M} ]
is sufficiently fast.
In the code, for further optimization, all operations are read in advance, and the processing cost is estimated for multiple candidate block sizes to choose the best one.
This is an optimization to improve execution time; the essence of the algorithm is square root decomposition.
Complexity
Let \(M=N-K+1\) and the block size be \(B\).
- Initial computation: \(O(N)\)
- Block construction: \(O(M \log B)\)
- One rent change: \(O(B + M/B)\)
- One query: \(O((M/B)\log B)\)
Therefore, with \(B \approx \sqrt{M}\):
- Time complexity: \(O(N + M\log M + Q\sqrt{M}\log M)\)
- Space complexity: \(O(N+Q)\)
Considering only the data structure part, the space complexity is \(O(M)\).
Implementation Notes
- The total rent can be as large as \(10^5 \times 10^9 = 10^{14}\), so
long longmust be used. - The input is \(1\)-indexed, but the implementation converts to \(0\)-indexed.
- The range of candidates affected by a rent change is
[ [\max(0,p-K+1), \min(p,M-1)] ]
Since the order of \(P_l\) within each block does not change, there is no need to re-sort during updates.
Additions to the entire block are stored in
lazy, and only for partial updates are actual values updated and the suffix minimum rebuilt.To determine when no answer exists, it is convenient to keep track of the maximum \(P_l\) across all candidates.
Source Code
#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;
}
This editorial was generated by gpt-5.5-high.
posted:
last update: