Overview

This problem involves handling a mix of “range addition” and “closure (deletion)” operations on moisture values \(C_i\) for each plot, while efficiently computing the sum of harvest values \(S_i\) for plots within a given interval that are “not closed and have \(C_i \le 0\) (dried out).”

Analysis

Key Observations

• The dryness check is a threshold condition: “moisture is at most \(0\)”, i.e., \(C_i \le 0\).
• Since range additions add the same value \(v\), if we can add to an entire group (block) at once, using lazy addition is efficient.
• Furthermore, if we keep the (non-closed) elements within a block sorted in ascending order of \(C\), the number of elements satisfying “\(C_i + \text{lazy} \le 0\)” can be found via binary search, and the corresponding sum of \(S\) values can be obtained instantly from a precomputed prefix sum.

Why a Naive Approach Is Too Slow

Naively scanning the interval for each query gives \(O(N)\) for operation 3 (query) and \(O(N)\) for operation 1 (range addition), resulting in \(O(NQ)\) in the worst case. Even though the constraints are moderate, we need a mechanism that can handle “range addition + threshold aggregation + deletion” together for a more generally applicable solution.

Solution Strategy

• Divide the array into blocks of size approximately \(\sqrt{N}\) (square root decomposition).

• For each block:

  • Additions to the entire block are accumulated in lazy
  • Extract only “alive” elements, sort and store them as \((C,\ S)\) pairs in ascending order of \(C\)
  • Build a prefix sum prefS of \(S\) values in the sorted order

• For queries, blocks entirely contained in the range are handled instantly via binary search; only the partial blocks at the endpoints are scanned naively.

Algorithm

1. Square Root Decomposition (Block Decomposition)

Partition indices \([0, N)\) into blocks of size \(B \approx \sqrt{N}\). Each block maintains:

• C[i]: base moisture value excluding lazy
• S[i]: harvest value
• alive[i]: whether the plot is not closed
• lazy: the uniform lazy addition applied to the entire block
• sortedC: array of C values of alive elements, sorted in ascending order
• prefS: prefix sum of \(S\) values in the same order as sortedC (prefS[k] is the sum of the first \(k\) values of \(S\))

2. Block Reconstruction rebuild()

When partial updates (additions to endpoint blocks) or deletions occur, the internal block information becomes invalid and must be rebuilt.

• Collect only alive elements into an array of \((C_i, S_i)\) pairs
• Sort by \(C_i\)
• Construct sortedC and prefS

Here, C values remain as base values without lazy (lazy is managed separately).

3. Operation 1: Range Addition 1 l r v

Add \(v\) to the interval \([l, r)\).

• For the left-end block and right-end block (or just one block if they are the same), directly update C[i] += v for elements in the target range, then rebuild()
• For blocks completely contained in between, simply do lazy += v (no reconstruction needed)

※ Even when partially updating a block that already has a lazy value, since the actual value is \((C_i + lazy)\): \((C_i + lazy) + v = (C_i + v) + lazy\) So C[i] += v correctly handles this.

4. Operation 2: Deletion 2 x

Close plot \(x\) (set alive to False), then rebuild() that block.

5. Operation 3: Query 3 l r

Sum of \(S_i\) for plots in interval \([l, r)\) that are “alive and \((C_i + lazy) \le 0\)”.

• For partial blocks at the endpoints, scan naively and check the condition
• For completely contained blocks, process in bulk:
  • Condition: \((C_i + lazy) \le 0 \iff C_i \le -lazy\)
  • Let t = -lazy, then k = bisect_right(sortedC, t) (number of elements \(\le t\))
  • The answer is prefS[k]

Example: For a block with lazy = 3, the dryness condition is: \(C_i + 3 \le 0 \iff C_i \le -3\) So we binary search sortedC for the range \(\le -3\), and immediately obtain the corresponding sum of \(S\) from prefS.

Complexity

Let the block size be \(B \approx \sqrt{N}\).

• Time complexity:
  • rebuild(): \(O(B \log B)\)
  • Operation 1 (range addition): \(O(B \log B)\) for endpoint blocks (including reconstruction) + \(O(\#\text{blocks})\) for middle blocks
  • Operation 2 (deletion): \(O(B \log B)\)
  • Operation 3 (query): \(O(B)\) for endpoint scanning + \(O(\log B)\) per middle block Overall, this runs in approximately \(O\big(Q(\sqrt{N}\log N)\big)\).
• Space complexity: \(O(N)\) (elements stored in blocks, and auxiliary arrays sortedC, prefS also total \(O(N)\))

Implementation Notes

• Manage C as base values excluding lazy, and store block-wide additions in lazy (do not mix them).

• Adding \(0\) at the beginning of prefS to make its length number of elements + 1 makes prefS[k] represent “the sum of the first \(k\) elements,” which is convenient.

• Using bisect_right(sortedC, t) gives “the number of elements \(\le t\)” (use right because the dryness condition is \(\le\)).

• After deletions or partial updates, always call rebuild() to keep sortedC and prefS up to date.

  Source Code

import sys
from bisect import bisect_right
import math

class Block:
    __slots__ = ("l", "r", "n", "S", "C", "alive", "lazy", "sortedC", "prefS")

    def __init__(self, l, r, S_all, C_all):
        self.l = l
        self.r = r
        self.n = r - l
        self.S = S_all[l:r]
        self.C = C_all[l:r]  # base values (lazy not included)
        self.alive = [True] * self.n
        self.lazy = 0
        self.sortedC = []
        self.prefS = [0]
        self.rebuild()

    def rebuild(self):
        arr = [(self.C[i], self.S[i]) for i in range(self.n) if self.alive[i]]
        arr.sort()
        self.sortedC = [c for c, _ in arr]
        pref = [0]
        s = 0
        for _, v in arr:
            s += v
            pref.append(s)
        self.prefS = pref

    def query_all(self):
        # sum S for alive with (C + lazy) <= 0  <=>  C <= -lazy
        t = -self.lazy
        k = bisect_right(self.sortedC, t)
        return self.prefS[k]


def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    Q = int(next(it))
    S = [int(next(it)) for _ in range(N)]
    C = [int(next(it)) for _ in range(N)]

    B = int(math.isqrt(N)) + 1
    blocks = []
    block_id = [0] * N
    for start in range(0, N, B):
        end = min(N, start + B)
        blk = Block(start, end, S, C)
        bid = len(blocks)
        blocks.append(blk)
        for i in range(start, end):
            block_id[i] = bid

    out = []

    for _ in range(Q):
        t = int(next(it))
        if t == 1:
            l = int(next(it)) - 1
            r = int(next(it))  # exclusive
            v = int(next(it))
            if l >= r:
                continue
            bl = block_id[l]
            br = block_id[r - 1]
            if bl == br:
                blk = blocks[bl]
                L = l - blk.l
                R = r - blk.l
                c = blk.C
                for i in range(L, R):
                    c[i] += v
                blk.rebuild()
            else:
                blk = blocks[bl]
                L = l - blk.l
                R = blk.r - blk.l
                c = blk.C
                for i in range(L, R):
                    c[i] += v
                blk.rebuild()

                for b in range(bl + 1, br):
                    blocks[b].lazy += v

                blk = blocks[br]
                L = 0
                R = r - blk.l
                c = blk.C
                for i in range(L, R):
                    c[i] += v
                blk.rebuild()

        elif t == 2:
            x = int(next(it)) - 1
            b = block_id[x]
            blk = blocks[b]
            idx = x - blk.l
            blk.alive[idx] = False
            blk.rebuild()

        else:  # t == 3
            l = int(next(it)) - 1
            r = int(next(it))  # exclusive
            if l >= r:
                out.append("0")
                continue
            bl = block_id[l]
            br = block_id[r - 1]
            ans = 0
            if bl == br:
                blk = blocks[bl]
                L = l - blk.l
                R = r - blk.l
                lazy = blk.lazy
                c = blk.C
                s = blk.S
                alive = blk.alive
                for i in range(L, R):
                    if alive[i] and c[i] + lazy <= 0:
                        ans += s[i]
            else:
                blk = blocks[bl]
                L = l - blk.l
                R = blk.r - blk.l
                lazy = blk.lazy
                c = blk.C
                s = blk.S
                alive = blk.alive
                for i in range(L, R):
                    if alive[i] and c[i] + lazy <= 0:
                        ans += s[i]

                for b in range(bl + 1, br):
                    ans += blocks[b].query_all()

                blk = blocks[br]
                L = 0
                R = r - blk.l
                lazy = blk.lazy
                c = blk.C
                s = blk.S
                alive = blk.alive
                for i in range(L, R):
                    if alive[i] and c[i] + lazy <= 0:
                        ans += s[i]

            out.append(str(ans))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.