K - 商店街の区画選び / Choosing Blocks in a Shopping Street Editorial by admin
gpt-5.5-xhighOverview
This is a problem where you choose one contiguous interval of length \(K\), and among intervals that satisfy the parking space count condition, you find the minimum total rent.
The rent \(A_i\) is updated, but the presence or absence of parking spaces \(C_i\) does not change, so the number of parking spaces in each interval of length \(K\) can be computed initially and kept fixed.
Analysis
Let \(l\) be the starting position of an interval of length \(K\).
For the interval \([l, l+K-1]\), define:
- Total rent as \(S_l\)
- Number of parking spaces as \(P_l\)
Then each query becomes:
Among starting positions \(l\) satisfying \(P_l \geq X\), find the minimum value of \(S_l\)
The total number of intervals of length \(K\) is
\[ M = N - K + 1 \]
Naive Approach
If we check all intervals of length \(K\) for each query, it takes \(O(N)\).
Also, when \(A_i\) changes due to a rent update, the total rent of all intervals of length \(K\) containing that section changes. Since up to \(K\) intervals are affected, directly updating each time takes \(O(K)\).
The constraints are \(N \leq 10^5\), \(Q \leq 5 \times 10^4\), so naive processing won’t be fast enough.
Key Insight
Only \(S_l\) changes due to rent updates.
On the other hand, the parking space count \(P_l\) remains fixed from start to finish since \(C_i\) doesn’t change.
Thus, the required operations are of two types:
- Add the same value to \(S_l\) over a contiguous range
- Find the minimum \(S_l\) among \(l\) satisfying \(P_l \geq X\)
We manage this with square root decomposition.
Algorithm
1. Precompute each interval of length \(K\)
Using prefix sums, for each starting position \(l\), compute:
\[ S_l = A_l + A_{l+1} + \cdots + A_{l+K-1} \]
\[ P_l = C_l + C_{l+1} + \cdots + C_{l+K-1} \]
In the implementation, we use 0-indexed, so starting positions satisfy \(0 \leq l < M\).
2. Range affected by rent updates
Suppose the rent at section \(pos\) changes by \(\Delta\).
The starting positions \(l\) of intervals of length \(K\) that contain this section satisfy:
\[ l \leq pos \leq l+K-1 \]
Rearranging:
\[ pos-K+1 \leq l \leq pos \]
Therefore, the actual range is:
\[ \max(0, pos-K+1) \leq l \leq \min(pos, M-1) \]
We need to add \(\Delta\) to all \(S_l\) in this range.
3. Managing with square root decomposition
We divide starting positions \(l\) into blocks.
For each block, we maintain the following information:
- The starting positions contained in that block
- The parking space count \(P_l\) for each starting position
- An index array sorted in ascending order of \(P_l\)
- Suffix minimums over that sorted order
- A lazy value
lazyrepresenting the amount added to the entire block
What is suffix minimum?
We sort the starting positions within a block in ascending order of \(P_l\).
For example, suppose within a block we have:
| Sort order | \(P_l\) | \(S_l\) |
|---|---|---|
| 0 | 1 | 100 |
| 1 | 2 | 80 |
| 2 | 3 | 120 |
| 3 | 5 | 70 |
If a query with \(X=3\) comes, we only want to look at those with \(P_l \geq 3\), so positions from sort order 2 onwards are targets.
Therefore, if we maintain:
\[ suff[i] = \text{minimum } S_l \text{ from position } i \text{ onwards} \]
then we can binary search for the first position where \(P_l \geq X\), and just look at the suff value at that position to get the answer for that block.
4. Range addition
When performing range addition on \(S_l\), the target range may span multiple blocks.
If the entire block is contained within the range:
→ Just add tolazy.If only part of the block is within the range:
→ Directly update the target \(S_l\) values and rebuild the suffix minimum for that block.
Since the parking space count \(P_l\) doesn’t change, the sorted order doesn’t need to be rebuilt.
5. Query processing
For a query \(X\), we examine all blocks.
For each block:
- Binary search for the first position where \(P_l \geq X\)
- Get the minimum \(S_l\) from that position onwards using
suff - Add the block’s lazy value
lazy
We do this for all blocks and return the minimum.
If no interval satisfies the condition, output IMPOSSIBLE.
Complexity
Let \(M = N-K+1\) and block size be \(B\).
- Initialization: \(O(M \log B)\)
- One rent update: \(O(B + M/B)\)
- One query: \(O((M/B) \log B)\)
- Space complexity: \(O(M)\)
In this implementation, \(B=512\), and since \(M \leq 10^5\), it runs sufficiently fast.
Implementation Notes
- Input is 1-indexed, but the implementation converts to 0-indexed.
- When updating rent, we compute the difference from the original value:
$\( \Delta = Y - A_{pos} \)$
and add only that difference to the affected intervals.
Since the parking space count \(P_l\) is never updated, the array sorted by \(P_l\) within each block only needs to be constructed once at the beginning.
Addition to an entire block is accumulated in
lazy, and suffix minimums are rebuilt only when a partial update occurs.Source Code
#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;
}
This editorial was generated by gpt-5.5-xhigh.
posted:
last update: