Overview

This problem gives a sequence \(A\) of length \(N\) (rents) and a sequence \(C\) of length \(N\) (presence/absence of parking spaces). For contiguous subsequences of length \(K\) (ways to choose sections), among those with at least \(X\) parking spaces, we need to find the minimum total rent. However, since rent values \(A_i\) can be modified by queries during the process, we need to manage values dynamically.

Analysis

The number of ways to choose \(K\) consecutive sections is \(M = N-K+1\) in total, where the left endpoint index is \(l\) (\(1 \leq l \leq N-K+1\)). For each choice \(l\), we define the following two values: - \(P_l\): the number of parking spaces (\(C_l + \dots + C_{l+K-1}\)) - \(S_l\): the total rent (\(A_l + \dots + A_{l+K-1}\))

For answer queries, we need to find “the minimum value of \(S_l\) among all \(l\) satisfying \(P_l \ge X\).” Here, an important property is that the presence/absence of parking spaces \(C_i\) never changes, so the value of \(P_l\) for each choice \(l\) is invariant (fixed). On the other hand, when a rent update query changes \(A_x\) to \(y\), the values of \(S_l\) for all choices \(l\) that include section \(x\) (i.e., \(x-K+1 \le l \le x\)) change by \(y - A_x\). This corresponds to a “range addition” on \(S_l\).

If we naively update \(S_l\) and find the minimum each time, it takes \(O(N)\) per query, resulting in \(O(QN)\) overall, which exceeds the time limit (TLE). To efficiently handle this combination of “a condition \(P_l \ge X\) on fixed keys \(P_l\)” and “range addition and minimum value retrieval on dynamically changing values \(S_l\)”, we apply Square Root Decomposition.

Algorithm

We divide the \(M\) choices into buckets (groups) of size \(B\). The number of buckets is \(D = \lceil M / B \rceil\).

1. Initialization

Within each bucket, sort the elements in ascending order of \(P_l\). - Let the sorted indices be sorted_l and the corresponding parking space counts be sorted_P. - Furthermore, build an array suffix_min that maintains the “suffix minimum” of \(S_l\) in the sorted order. - suffix_min[i] = \(\min_{j \ge i} S_{\text{sorted\_l}[j]}\) - With this, if we find the smallest index \(idx\) where \(P_l \ge X\) in a bucket using binary search, the minimum value of \(S_l\) satisfying the condition within that bucket can be obtained as suffix_min[idx] in \(O(1)\).

2. Rent Update Query (\(T_j = 1\))

When the rent of section \(x\) is changed to \(y\), compute the difference \(d = y - A_x\). The range of affected \(S_l\) values is the contiguous interval \([QL, QR] = [\max(0, x-K), \min(M-1, x-1)]\) (0-indexed). This is processed similarly to a standard range update in square root decomposition. - Fully contained buckets: Add \(d\) to the variable add[bid] representing the cumulative addition for the entire bucket. - Partially contained buckets (edge buckets): - For elements \(l\) within the range, individually update \(S_l \leftarrow S_l + d\). - Then, rebuild the suffix_min for that bucket. Since the order of \(P_l\) does not change, there is no need to re-sort; only the suffix minimum array needs to be recomputed, which takes \(O(B)\).

3. Answer Query (\(T_j = 2\))

For all \(D\) buckets, do the following: - In the bucket’s sorted_P, find the smallest index \(idx\) where the value is at least \(X\) using binary search (bisect_left). - If \(idx\) is less than the bucket size, take suffix_min[idx] + add[bid] as a candidate for the minimum within that bucket, and update the overall minimum. - The minimum value after searching all buckets is the answer. If no candidate was found at all, output IMPOSSIBLE.

Complexity

Let the bucket size be \(B \approx \sqrt{M}\).

• Time Complexity: \(O(M \log M + Q \sqrt{M} \log M)\)
  • Initialization: Sorting each of the \(D\) buckets of size \(B\) takes \(O(D \cdot B \log B) = O(M \log B)\) overall.
  • Rent Update Query: Updating fully contained buckets takes \(O(D)\), and updating and rebuilding edge buckets takes \(O(B)\), so each query costs \(O(D + B) = O(\frac{M}{B} + B)\).
  • Answer Query: Binary search is performed on each of the \(D\) buckets, so each query costs \(O(D \log B) = O(\frac{M}{B} \log B)\).
  • By setting \(B \approx \sqrt{M}\), each query can be processed efficiently in approximately \(O(\sqrt{M} \log M)\).
• Space Complexity: \(O(N + Q)\)
  • The memory required to store the original arrays and per-bucket information is linear with respect to the number of elements \(N\) and the number of queries \(Q\).

Implementation Notes

• Choosing the bucket size \(B\):

  • Theoretically, \(B = \sqrt{M}\) is optimal, but considering Python’s overhead, fixing \(B\) at around \(500\) achieves the best balance between the number of binary searches (number of buckets \(D\)) and the cost of rebuilding (bucket size \(B\)), resulting in fast execution.

• Speeding up rebuilding (rebuild):

  • When updating edge buckets, the sort order within the bucket (sorted_l) does not change. Therefore, we can completely skip the sorting step and only update the suffix_min array by scanning from the back, significantly reducing the constant factor.

    Source Code

import bisect
import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    K = int(data[1])
    Q = int(data[2])

    A = [0] + [int(x) for x in data[3 : 3 + N]]
    C = [0] + [int(x) for x in data[3 + N : 3 + 2 * N]]

    queries = []
    idx = 3 + 2 * N
    for _ in range(Q):
        t = int(data[idx])
        x = int(data[idx + 1])
        y = int(data[idx + 2])
        queries.append((t, x, y))
        idx += 3

    pref_C = [0] * (N + 1)
    for i in range(1, N + 1):
        pref_C[i] = pref_C[i - 1] + C[i]

    pref_A = [0] * (N + 1)
    for i in range(1, N + 1):
        pref_A[i] = pref_A[i - 1] + A[i]

    M = N - K + 1
    P = [0] * M
    S = [0] * M
    for l in range(M):
        P[l] = pref_C[l + K] - pref_C[l]
        S[l] = pref_A[l + K] - pref_A[l]

    B = 500
    num_buckets = (M + B - 1) // B

    bucket_start = [i * B for i in range(num_buckets)]
    bucket_end = [min(M, (i + 1) * B) for i in range(num_buckets)]
    sorted_l = [[] for _ in range(num_buckets)]
    sorted_P = [[] for _ in range(num_buckets)]
    suffix_min = [[] for _ in range(num_buckets)]
    add = [0] * num_buckets

    for bid in range(num_buckets):
        start = bucket_start[bid]
        end = bucket_end[bid]
        l_list = list(range(start, end))
        l_list.sort(key=lambda l: P[l])
        sorted_l[bid] = l_list
        sorted_P[bid] = [P[l] for l in l_list]

        sz = end - start
        s_min = [0] * sz
        if sz > 0:
            s_min[-1] = S[l_list[-1]]
            for i in range(sz - 2, -1, -1):
                val = S[l_list[i]]
                nxt = s_min[i + 1]
                s_min[i] = val if val < nxt else nxt
        suffix_min[bid] = s_min

    INF = 10**18

    def rebuild(bid, sorted_l_bid, suffix_min_bid, S):
        sz = len(sorted_l_bid)
        if sz > 0:
            suffix_min_bid[-1] = S[sorted_l_bid[-1]]
            for i in range(sz - 2, -1, -1):
                val = S[sorted_l_bid[i]]
                nxt = suffix_min_bid[i + 1]
                suffix_min_bid[i] = val if val < nxt else nxt

    out = []
    bisect_left = bisect.bisect_left

    for t, x, y in queries:
        if t == 1:
            d = y - A[x]
            A[x] = y
            QL = max(0, x - K)
            QR = min(M - 1, x - 1)
            if QL <= QR:
                bid_L = QL // B
                bid_R = QR // B
                if bid_L == bid_R:
                    for l in range(QL, QR + 1):
                        S[l] += d
                    rebuild(bid_L, sorted_l[bid_L], suffix_min[bid_L], S)
                else:
                    for l in range(QL, bucket_end[bid_L]):
                        S[l] += d
                    rebuild(bid_L, sorted_l[bid_L], suffix_min[bid_L], S)
                    for bid in range(bid_L + 1, bid_R):
                        add[bid] += d
                    for l in range(bucket_start[bid_R], QR + 1):
                        S[l] += d
                    rebuild(bid_R, sorted_l[bid_R], suffix_min[bid_R], S)
        else:
            ans = INF
            for bid in range(num_buckets):
                s_P = sorted_P[bid]
                idx = bisect_left(s_P, x)
                if idx < len(s_P):
                    val = suffix_min[bid][idx] + add[bid]
                    if val < ans:
                        ans = val
            if ans == INF:
                out.append("IMPOSSIBLE")
            else:
                out.append(str(ans))

    print("\n".join(out))


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.