K - 商店街の区画選び / Choosing Blocks in a Shopping Street Editorial by admin
gpt-5.5-highOverview
When selecting one contiguous segment of length \(K\), we find the minimum total rent among those segments that satisfy the condition on the number of sections with parking spaces.
We utilize the fact that while rents \(A_i\) are updated, the parking space availability \(C_i\) does not change.
Approach
Let \(i\) be the starting position of a segment of length \(K\).
- \(S_i\): the total rent of the length-\(K\) segment starting at position \(i\)
- \(P_i\): the number of sections with parking spaces in the length-\(K\) segment starting at position \(i\)
Then, the answer to a query \(X\) is
\[ S_i \]
minimized over all segments satisfying
\[ P_i \geq X \]
The key insight here is that since \(C_i\) is never updated, the value \(P_i\) for each segment remains unchanged from start to finish.
On the other hand, when a rent \(A_x\) is updated, the \(S_i\) of all length-\(K\) segments containing it change by the same difference.
For example, suppose \(A_x\) changes by \(d\).
The starting positions \(i\) of affected segments satisfy
\[ i \leq x \leq i+K-1 \]
In other words, the starting positions \(i\) form a contiguous range.
Therefore, updates can be treated as “range addition” on the array \(S\).
The problem can be rephrased as follows:
- Perform range addition on the array \(S_i\)
- For fixed values \(P_i\), find the minimum \(S_i\) among all \(i\) satisfying \(P_i \geq X\)
Naively checking all segments for each query takes \(O(N)\), resulting in approximately \(5 \times 10^9\) operations, which is too slow.
Therefore, we manage the starting positions using square root decomposition.
Algorithm
The total number of length-\(K\) segments is
\[ M = N-K+1 \]
First, for each starting position \(i\), we compute
- Total rent \(S_i\)
- Number of parking spaces \(P_i\)
in \(O(N)\) by sliding like a two-pointer technique.
After that, we divide starting positions \(0,1,\dots,M-1\) into blocks.
For each block, we maintain the following:
- An array of starting positions within that block sorted in ascending order of \(P_i\)
- The \(P_i\) values in sorted order
- A suffix minimum array
For example, suppose a block has \(P_i\) values sorted in ascending order:
\[ [0, 1, 3, 3] \]
and the corresponding \(S_i\) values are:
\[ [8, 5, 10, 7] \]
Then the suffix minimums are:
\[ [5, 5, 7, 7] \]
If a query asks for “\(P_i \geq 2\)”, we binary search for the first position where \(P_i \geq 2\).
In this example, we look from the position where \(P_i=3\), so the answer candidate is \(7\).
Update Processing
Suppose we change rent \(A_x\) to \(Y\).
The difference is
\[ d = Y - A_x \]
This \(d\) is added to all length-\(K\) segments containing \(x\).
That is, we perform range addition on a contiguous range of \(S_i\).
In square root decomposition, we handle the update range as follows:
- Blocks completely contained within the range
→ We simply add the same value to the entire block, recording it as a lazy addition - Blocks at the boundaries that are only partially contained
→ We actually update each \(S_i\) and reconstruct the suffix minimum array for that block
This way, at most 2 blocks need to be reconstructed per update.
Query Processing
For a query \(X\), we examine each block.
For a given block:
- If the maximum \(P_i\) in the block is less than \(X\), there are no segments in that block satisfying the condition
- Otherwise, binary search on the sorted \(P_i\) array to find the first position where \(P_i \geq X\)
- Retrieve the minimum \(S_i\) from that position onward using the suffix minimum array
- Add the lazy addition value for the entire block
We do this for all blocks and output the minimum.
Additionally, if we maintain max_parking as the overall maximum number of parking spaces, queries with \(X > \text{max\_parking}\) can be immediately answered as IMPOSSIBLE.
Complexity
Let \(M=N-K+1\), block size be \(B\), number of updates be \(U\), and number of valid queries be \(R\).
- Initial computation: \(O(N)\)
- Sorting each block: \(O(M \log B)\)
- One update: \(O(B)\)
- One query: \(O\left(\frac{M}{B}\log B\right)\)
Therefore, the overall complexity is
\[ O\left(N + M\log B + UB + R\frac{M}{B}\log B\right) \]
Setting the block size to approximately \(\sqrt{M}\), this typically runs in
\[ O\left((N+Q)\sqrt{N}\log N\right) \]
- Time complexity: \(O\left(N + M\log B + UB + R\frac{M}{B}\log B\right)\)
- Space complexity: \(O(M)\)
Implementation Notes
- The length-\(K\) segment sums \(S_i\) and parking space counts \(P_i\) are computed in \(O(N)\) by sliding.
- The range of starting positions affected by an update, in 0-indexed terms, is
$\( [x-K+1, x] \)$
clamped to the valid array range.
Within each block, the order of \(P_i\) does not change.
Only \(S_i\) changes, so there is no need to re-sort after updates.When the same value is added to an entire block, the position achieving the minimum does not change, so it can be managed as a lazy addition.
Only partially updated blocks need their suffix minimum arrays recomputed.
When \(X > \text{max\_parking}\), no segment satisfies the condition, so we can immediately output
IMPOSSIBLE.Source Code
import sys
from bisect import bisect_left
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
if not data:
return
p = 0
N = data[p]
K = data[p + 1]
Q = data[p + 2]
p += 3
A = data[p:p + N]
p += N
C = data[p:p + N]
p += N
op_start = p
op_end = op_start + 3 * Q
M = N - K + 1
vals = [0] * M
s = sum(A[:K])
vals[0] = s
for i in range(1, M):
s += A[i + K - 1] - A[i - 1]
vals[i] = s
cnt = [0] * M
c = sum(C[:K])
cnt[0] = c
for i in range(1, M):
c += C[i + K - 1] - C[i - 1]
cnt[i] = c
max_parking = max(cnt)
upd_count = 0
possible_query_count = 0
for i in range(op_start, op_end, 3):
if data[i] == 1:
upd_count += 1
else:
if data[i + 1] <= max_parking:
possible_query_count += 1
if possible_query_count == 0:
out = []
for i in range(op_start, op_end, 3):
if data[i] == 2:
out.append("IMPOSSIBLE")
sys.stdout.write("\n".join(out))
return
if upd_count == 0:
B = M
else:
B = int((2.0 * possible_query_count * M / upd_count) ** 0.5) + 1
if B < 16:
B = 16
if B > M:
B = M
nb = (M + B - 1) // B
INF = 10 ** 30
starts = [0] * nb
ends = [0] * nb
orders = []
cnt_blocks = []
sufs = []
min_counts = [0] * nb
max_counts = [0] * nb
getcnt = cnt.__getitem__
for b in range(nb):
st = b * B
en = st + B
if en > M:
en = M
starts[b] = st
ends[b] = en
idxs = list(range(st, en))
idxs.sort(key=getcnt)
cs = [cnt[i] for i in idxs]
sf = [0] * (en - st)
cur = INF
for j in range(len(idxs) - 1, -1, -1):
v = vals[idxs[j]]
if v < cur:
cur = v
sf[j] = cur
orders.append(idxs)
cnt_blocks.append(cs)
sufs.append(sf)
min_counts[b] = cs[0]
max_counts[b] = cs[-1]
block_diff = [0] * (nb + 1)
def add_part(b, lo, hi, d):
vv = vals
for ii in range(lo, hi):
vv[ii] += d
idxs = orders[b]
sf = sufs[b]
cur_min = INF
for jj in range(len(idxs) - 1, -1, -1):
v = vv[idxs[jj]]
if v < cur_min:
cur_min = v
sf[jj] = cur_min
out = []
append = out.append
bl = bisect_left
for ptr in range(op_start, op_end, 3):
t = data[ptr]
x = data[ptr + 1]
if t == 1:
y = data[ptr + 2]
xi = x - 1
old = A[xi]
if old == y:
continue
d = y - old
A[xi] = y
l = x - K
if l < 0:
l = 0
r = x - 1
if r >= M:
r = M - 1
b1 = l // B
b2 = r // B
rp1 = r + 1
if b1 == b2:
if l == starts[b1] and rp1 == ends[b1]:
block_diff[b1] += d
block_diff[b1 + 1] -= d
else:
add_part(b1, l, rp1, d)
else:
lf = b1
if l != starts[b1]:
add_part(b1, l, ends[b1], d)
lf = b1 + 1
rg = b2
if rp1 != ends[b2]:
add_part(b2, starts[b2], rp1, d)
rg = b2 - 1
if lf <= rg:
block_diff[lf] += d
block_diff[rg + 1] -= d
else:
need = x
if need > max_parking:
append("IMPOSSIBLE")
continue
ans = INF
lazy = 0
for b in range(nb):
lazy += block_diff[b]
if need <= min_counts[b]:
v = sufs[b][0] + lazy
if v < ans:
ans = v
elif need <= max_counts[b]:
pos = bl(cnt_blocks[b], need)
v = sufs[b][pos] + lazy
if v < ans:
ans = v
if ans == INF:
append("IMPOSSIBLE")
else:
append(str(ans))
sys.stdout.write("\n".join(out))
if __name__ == "__main__":
main()
This editorial was generated by gpt-5.5-high.
posted:
last update: