Overview

This problem involves processing the following three types of queries efficiently on \(N\) shelves arranged in a row: 1. Add \(1\) book to every shelf in the interval \([l, r]\) (range addition) 2. Remove all books from shelf \(p\), setting the count to \(0\) (point update) 3. Find the total number of books in the interval \([l, r]\) (range sum query)

To efficiently perform addition and sum queries over intervals, we use a Lazy Segment Tree.

---

Analysis

1. Naive Approach and Its Limitations

Consider managing the shelf states naively using an array. - Task 1 (range addition): Use a loop to add \(1\) to shelves \(l\) through \(r\). This takes \(O(N)\) in the worst case. - Task 2 (point clear): Set the value of shelf \(p\) to \(0\). This is \(O(1)\). - Task 3 (range sum query): Use a loop to compute the sum from shelf \(l\) to \(r\). This takes \(O(N)\) in the worst case.

The number of operations \(Q\) can be up to \(2 \times 10^5\), and the number of shelves \(N\) can also be up to \(2 \times 10^5\), so the overall worst-case time complexity is \(O(NQ)\), which will not fit within the time limit (resulting in TLE). Therefore, we need a data structure that can process each query in approximately \(O(\log N)\) time.

2. Introducing the Lazy Segment Tree

The representative data structure that can efficiently perform both “range addition” and “range sum query” simultaneously is the Lazy Segment Tree.

However, this problem includes the operation “Task 2: Set the value of a specific shelf \(p\) to \(0\)”. In general, when trying to handle both “range addition” and “range assignment (assigning \(0\))” simultaneously in a lazy segment tree, the design of the lazy operators (deferred operations) becomes complex, increasing implementation difficulty.

3. Reinterpreting the “Set to 0” Operation

Here, we consider reinterpreting “setting a shelf’s value to \(0\)” as “retrieving the current value \(v\) and adding \(-v\) to that shelf”.

Specifically, we perform Task 2 (setting shelf \(p\)’s value to \(0\)) in the following two steps: 1. Retrieve the current number of books \(v\) on shelf \(p\) (this is equivalent to getting the sum of the interval \([p, p+1)\)). 2. Add \(-v\) to shelf \(p\) (interval \([p, p+1)\)).

By reinterpreting it this way, we can unify the operations on the data structure into just two types: “range addition” and “range sum query”. This makes it possible to design and implement the lazy segment tree very simply.

---

Algorithm

We define the monoid (data type) and the operator (update query type) to be used in the lazy segment tree as follows.

1. Segment Tree Elements (struct S)

Each node holds the following two pieces of information: - val: The total number of books in the interval - len: The length of the interval (number of shelves)

Binary operation op(a, b) Combines the information of the left and right child nodes. - The total book count is the sum of the left and right totals: a.val + b.val - The interval length is the sum of the left and right lengths: a.len + b.len

Identity element e() Represents an empty interval. - {0, 0} (total count 0, interval length 0)

2. Operator (type F)

An integer (long long) representing the value to add.

Mapping mapping(f, x) Adds value f uniformly to a node whose interval length is x.len. - The new total count is the original total plus “the value to add \(\times\) the interval length”: x.val + f * x.len

Composition of operators composition(f, g) Adds operation f on top of a node that already has a deferred operation g. - The final value to add is simply their sum: f + g

Identity mapping id() Represents adding nothing. - 0

---

Complexity

• Time Complexity: \(O(Q \log N)\)
  • Each operation (apply, prod) on the lazy segment tree runs in \(O(\log N)\) time, proportional to the height of the tree.
  • Task 2 calls prod and apply once each, which is also \(O(\log N)\).
  • Since there are \(Q\) queries, the overall complexity is \(O(Q \log N)\), which comfortably fits within the time limit.
• Space Complexity: \(O(N)\)
  • The memory required to build the segment tree is linear (\(O(N)\)) with respect to the number of shelves \(N\).

---

Implementation Notes

• Conversion to 0-indexed The shelf numbers \(l, r, p\) given in the input are 1-indexed (numbered starting from 1), but internally in the program (segment tree) they are handled as 0-indexed (numbered starting from 0). Therefore, after receiving the input, we need to perform l-- or p--.

• Conversion to half-open intervals Segment tree query ranges are generally specified as half-open intervals \([l, r)\) (from \(l\) inclusive to \(r\) exclusive). Since the problem’s queries use closed intervals \([l, r]\) (from \(l\) inclusive to \(r\) inclusive), by passing the right endpoint index as \(r\) without decrementing (not subtracting 1), we can correctly process it as the half-open interval \([l-1, r)\).

  Source Code

#include <iostream>
#include <vector>

using namespace std;

struct S {
    long long val;
    int len;
};

using F = long long;

S op(S a, S b) {
    return S{a.val + b.val, a.len + b.len};
}

S e() {
    return S{0, 0};
}

S mapping(F f, S x) {
    return S{x.val + f * x.len, x.len};
}

F composition(F f, F g) {
    return f + g;
}

F id() {
    return 0;
}

struct LazySegTree {
    int n;
    int size;
    int log;
    vector<S> d;
    vector<F> lz;

    LazySegTree(int n) : n(n) {
        log = 0;
        while ((1 << log) < n) log++;
        size = 1 << log;
        d.assign(2 * size, e());
        lz.assign(size, id());
        for (int i = 0; i < n; i++) d[size + i] = S{0, 1};
        for (int i = size - 1; i >= 1; i--) update(i);
    }

    void update(int k) {
        d[k] = op(d[2 * k], d[2 * k + 1]);
    }

    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }

    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }

    void apply(int l, int r, F f) {
        if (l == r) return;
        l += size;
        r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    S prod(int l, int r) {
        if (l == r) return e();
        l += size;
        r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, q;
    if (!(cin >> n >> q)) return 0;
    
    LazySegTree seg(n);
    
    for (int i = 0; i < q; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            l--; 
            seg.apply(l, r, 1);
        } else if (type == 2) {
            int p;
            cin >> p;
            p--; 
            long long val = seg.prod(p, p + 1).val;
            seg.apply(p, p + 1, -val);
        } else if (type == 3) {
            int l, r;
            cin >> l >> r;
            l--; 
            cout << seg.prod(l, r).val << "\n";
        }
    }
    return 0;
}

---

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