Overview

This problem asks us to efficiently compute, among all ways to choose \(K\) consecutive sections of a shopping street (\(N - K + 1\) ways in total), the “minimum total rent among choices that have at least \(X\) parking spaces,” while reflecting rent changes (range additions).

To efficiently handle data updates and conditional minimum value queries, this can be solved using Square Root Decomposition.

---

Analysis

1. Problem Formulation

The ways to choose \(K\) consecutive sections can be indexed by the leftmost section \(l\) \((0 \leq l \leq N-K)\), giving \(M = N - K + 1\) choices in total. For each choice \(l\), we define the following two values: - \(W_l\) : the sum of rents from the \(l\)-th to the \((l+K-1)\)-th section - \(S_l\) : the number of sections with parking spaces among the \(l\)-th to the \((l+K-1)\)-th sections

The initial values of \(W_l\) and \(S_l\) can be computed in \(O(N)\) overall using prefix sums or a sliding window technique.

2. Properties of Queries

• \(T = 1\) (Rent Change) The rent of the \(X\)-th section is changed to \(Y\), and we define the difference as \(d = Y - A_X\). This change affects the total rent of all consecutive \(K\) sections that include section \(X\). Specifically, \(d\) is added uniformly to all \(W_l\) where the left endpoint \(l\) satisfies \(\max(0, X - K + 1) \leq l \leq \min(M - 1, X)\). This is a range addition query on the array \(W\).

• \(T = 2\) (Question) Among all \(l\) satisfying \(S_l \ge X\), find the minimum value of \(W_l\). The key observation here is that since the parking availability \(C_i\) does not change, the values of \(S_l\) remain constant throughout all queries. On the other hand, the values of \(W_l\) change due to \(T=1\) queries.

3. Why Simple Approaches Are Too Slow

• Scanning all \(l\) for each question query takes \(O(N)\) per query, resulting in \(O(QN)\) overall, which exceeds the time limit (TLE).
• When using data structures such as segment trees, finding “the minimum value at positions where \(S_l \ge X\)” while performing range additions is difficult to manage in a straightforward way, since the condition is based on values (\(S_l\)) rather than indices.

4. Square Root Decomposition Approach

Leveraging the fact that \(S_l\) is fixed, we apply square root decomposition, dividing the array of \(M\) elements into blocks of size \(B \approx \sqrt{M}\).

For each block, we prepare the following precomputed table val: - val[s] : the minimum value of \(W_l\) among elements in that block satisfying \(S_l \geq s\)

By maintaining this table for each block, we can retrieve the conditional minimum from each block in \(O(1)\) for question queries.

---

Algorithm

1. Block Management and Construction (build)

For each block, we find the minimum \(S_{\min}\) and maximum \(S_{\max}\) of \(S_l\) within the block. Then, we construct an array val of size \(S_{\max} - S_{\min} + 1\) as follows:

1. Initialize all elements of val to infinity (\(\infty\)).
2. For each element \(l\) in the block, update val[S_l - S_min] = min(val[S_l - S_min], W_l).
3. Traverse \(s\) in reverse order from \(S_{\max} - 1\) down to \(S_{\min}\), and take cumulative minimums (suffix min): val[s - S_min] = min(val[s - S_min], val[s + 1 - S_min]).

As a result, val[s - S_min] stores “the minimum of \(W_l\) among elements in the block satisfying \(S_l \geq s\).” The time for this construction is \(O(B)\) relative to the block size \(B\).

2. Update Query (\(T = 1\))

Add value \(d\) to the range \([QL, QR]\). - Blocks fully contained in the range: Simply add \(d\) to the variable add representing the accumulated addition for the entire block, processed in \(O(1)\). - Blocks partially overlapping with the range: First, propagate (push) the add value to each element’s actual value W within the block, then directly add \(d\) to the elements within the range. Afterwards, call the build function for that block to reconstruct the table.

The computation per update is \(O(M/B + B)\) overall, since there are \(O(M/B)\) fully contained blocks and at most 2 partially overlapping blocks (each requiring \(O(B)\) for reconstruction).

3. Question Query (\(T = 2\))

Find the minimum value satisfying the condition \(S_l \geq X\). For each block \(b\), obtain a candidate in \(O(1)\) as follows, then take the overall minimum:

• If \(X \leq S_{\min}\): all elements in the block satisfy the condition, so the block’s overall minimum val[0] + add is a candidate.
• If \(S_{\min} < X \leq S_{\max}\): val[X - S_min] + add is a candidate.
• If \(X > S_{\max}\): no elements in the block satisfy the condition.

Since we scan all blocks, the computation per query is \(O(M/B)\).

---

Complexity

Set \(B = \sqrt{M}\).

• Time Complexity:

  • Initial construction: \(O(N)\)
  • Update query: \(O(\sqrt{N})\)
  • Question query: \(O(\sqrt{N})\)
  • Overall: \(O(N + Q \sqrt{N})\) Under the constraints \(N \leq 10^5, Q \leq 5 \times 10^4\), we have \(\sqrt{N} \approx 316\), so the total number of operations is approximately \(1.5 \times 10^7\), which comfortably fits within the time limit.

• Space Complexity:

  • The total size of all val arrays across all blocks is at most \(O(N)\).
  • Overall: \(O(N)\)

---

Implementation Notes

1. Timing of Lazy Propagation (push): When updating a partially overlapping block, always propagate the add value to each element’s W before performing individual updates, and clear add to \(0\). Failing to do so can cause past bulk additions to be lost or applied twice.

2. Index Offset: The values of \(S_l\) can range from \(0\) to \(K\), but the actual range within a block is contained in \([S_{\min}, S_{\max}]\). To save memory and speed up lookups, the val array indices are managed with an offset of \(S_{\min}\).

3. Index Boundaries: For \(T=1\) queries, the update range \([QL, QR]\) is \(QL = \max(0, X - K + 1)\) and \(QR = \min(M - 1, X)\) for section index \(X\). Be careful to clamp boundaries using max and min to avoid going out of bounds.

   Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const long long INF = 1e18;

struct Block {
    int L, R;
    long long add;
    vector<long long> W;
    vector<int> S;
    int S_min, S_max;
    vector<long long> val;

    void build() {
        int sz = S_max - S_min + 1;
        fill(val.begin(), val.end(), INF);
        for (int i = 0; i <= R - L; ++i) {
            int s = S[i];
            val[s - S_min] = min(val[s - S_min], W[i]);
        }
        for (int s = S_max - 1; s >= S_min; --s) {
            val[s - S_min] = min(val[s - S_min], val[s + 1 - S_min]);
        }
    }

    void push() {
        if (add != 0) {
            for (auto& w : W) w += add;
            add = 0;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, Q;
    if (!(cin >> N >> K >> Q)) return 0;

    vector<long long> 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];
    }

    int M = N - K + 1;

    vector<long long> init_W(M, 0);
    vector<int> init_S(M, 0);

    long long cur_W = 0;
    int cur_S = 0;
    for (int i = 0; i < K; ++i) {
        cur_W += A[i];
        cur_S += C[i];
    }
    init_W[0] = cur_W;
    init_S[0] = cur_S;

    for (int l = 1; l < M; ++l) {
        cur_W += A[l + K - 1] - A[l - 1];
        cur_S += C[l + K - 1] - C[l - 1];
        init_W[l] = cur_W;
        init_S[l] = cur_S;
    }

    int B = max(1, (int)sqrt(M));
    int D = (M + B - 1) / B;

    vector<Block> blocks(D);
    for (int b = 0; b < D; ++b) {
        blocks[b].L = b * B;
        blocks[b].R = min(M - 1, (b + 1) * B - 1);
        blocks[b].add = 0;
        int len = blocks[b].R - blocks[b].L + 1;
        blocks[b].W.resize(len);
        blocks[b].S.resize(len);
        blocks[b].S_min = K + 1;
        blocks[b].S_max = -1;
        for (int i = 0; i < len; ++i) {
            int l = blocks[b].L + i;
            blocks[b].W[i] = init_W[l];
            blocks[b].S[i] = init_S[l];
            blocks[b].S_min = min(blocks[b].S_min, blocks[b].S[i]);
            blocks[b].S_max = max(blocks[b].S_max, blocks[b].S[i]);
        }
        blocks[b].val.resize(blocks[b].S_max - blocks[b].S_min + 1);
        blocks[b].build();
    }

    auto update = [&](int QL, int QR, long long d) {
        for (int b = 0; b < D; ++b) {
            if (blocks[b].R < QL || QR < blocks[b].L) {
                continue;
            }
            if (QL <= blocks[b].L && blocks[b].R <= QR) {
                blocks[b].add += d;
            } else {
                blocks[b].push();
                int start = max(QL, blocks[b].L);
                int end = min(QR, blocks[b].R);
                for (int l = start; l <= end; ++l) {
                    blocks[b].W[l - blocks[b].L] += d;
                }
                blocks[b].build();
            }
        }
    };

    auto query = [&](int X) {
        long long ans = INF;
        for (int b = 0; b < D; ++b) {
            if (X <= blocks[b].S_min) {
                ans = min(ans, blocks[b].val[0] + blocks[b].add);
            } else if (X <= blocks[b].S_max) {
                ans = min(ans, blocks[b].val[X - blocks[b].S_min] + blocks[b].add);
            }
        }
        return ans;
    };

    for (int q = 0; q < Q; ++q) {
        int T;
        cin >> T;
        if (T == 1) {
            int X;
            long long Y;
            cin >> X >> Y;
            --X; // 0-indexed
            long long old = A[X];
            long long d = Y - old;
            A[X] = Y;
            int QL = max(0, X - K + 1);
            int QR = min(M - 1, X);
            update(QL, QR, d);
        } else {
            int X;
            long long Y;
            cin >> X >> Y; // Y is unused
            long long ans = query(X);
            if (ans >= INF) {
                cout << "IMPOSSIBLE\n";
            } else {
                cout << ans << "\n";
            }
        }
    }

    return 0;
}

---

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