概要

この問題は、一列に並んだ \(N\) 個の棚に対して、以下の3つのクエリを高速に処理する問題です。 1. 区間 \([l, r]\) のすべての棚に本を \(1\) 冊追加する（区間加算） 2. 棚 \(p\) の本をすべて取り除き、冊数を \(0\) にする（一点更新） 3. 区間 \([l, r]\) の本の合計冊数を求める（区間和取得）

区間に対する加算と和の取得を高速に行うために、遅延評価セグメント木（Lazy Segment Tree）を利用します。

---

考察

1. 素朴なアプローチとその限界

配列を用いて棚の状態を愚直に管理する場合を考えます。 - 作業 1（区間加算）：ループを用いて棚 \(l\) から \(r\) までに \(1\) を足す。最悪で \(O(N)\) かかります。 - 作業 2（一点クリア）：棚 \(p\) の値を \(0\) にする。これは \(O(1)\) です。 - 作業 3（区間和取得）：ループを用いて棚 \(l\) から \(r\) までの合計を計算する。最悪で \(O(N)\) かかります。

作業の回数 \(Q\) は最大で \(2 \times 10^5\)、棚の数 \(N\) も最大で \(2 \times 10^5\) であるため、全体での最悪時間計算量は \(O(NQ)\) となり、実行時間制限に間に合いません（TLEとなります）。 したがって、各クエリを \(O(\log N)\) 程度で高速に処理できるデータ構造が必要です。

2. 遅延評価セグメント木の導入

「区間加算」と「区間和取得」を同時に高速に行える代表的なデータ構造が遅延評価セグメント木（Lazy Segment Tree）です。

しかし、この問題には「作業 2：特定の棚 \(p\) の値を \(0\) にする」という操作があります。 一般に、遅延評価セグメント木で「区間加算」と「区間代入（\(0\) を代入する）」を同時に扱おうとすると、作用素（遅延させている操作）の設計が複雑になり、実装の難易度が上がります。

3. 「0にする」操作の言い換え

ここで、「ある棚の値を \(0\) にする」という操作を、「現在の値 \(v\) を取得し、その棚に \(-v\) を加算する」という操作に言い換えることを考えます。

具体的には、作業 2（棚 \(p\) の値を \(0\) にする）を以下の2ステップで行います。 1. 棚 \(p\) にある現在の本の冊数 \(v\) を取得する（これは区間 \([p, p+1)\) の和を取得することと同じです）。 2. 棚 \(p\)（区間 \([p, p+1)\)）に対して、\(-v\) を加算する。

このように言い換えることで、データ構造に対して行う操作を「区間加算」と「区間和取得」の2種類のみに統一することができます。これにより、遅延評価セグメント木を非常にシンプルに設計・実装することが可能になります。

---

アルゴリズム

遅延評価セグメント木にのせるモノイド（データの型）と作用素（更新クエリの型）を以下のように定義します。

1. セグ木の要素（構造体 S）

各ノードには、以下の2つの情報を持たせます。 - val: その区間の本の合計冊数 - len: その区間の長さ（棚の個数）

二項演算 op(a, b) 左右のノードの情報を結合します。 - 合計冊数は、左右の合計冊数の和になります：a.val + b.val - 区間の長さは、左右の長さの和になります：a.len + b.len

単位元 e() 空の区間を表します。 - {0, 0}（合計冊数 0、区間の長さ 0）

2. 作用素（型 F）

加算する値を表す整数（long long）とします。

作用 mapping(f, x) 区間の長さが x.len であるノードに、値 f を一斉に加算します。 - 新しい合計冊数は、元の合計冊数に「加算する値 \(\times\) 区間の長さ」を足したものになります：x.val + f * x.len

作用素の合成 composition(f, g) すでに g を加算する操作が遅延されているノードに、さらに f を加算する操作を追加します。 - 最終的に加算される値は、単純に足し合わされます：f + g

恒等写像 id() 何も加算しないことを表します。 - 0

---

計算量

• 時間計算量: \(O(Q \log N)\)
  • 遅延評価セグメント木の各操作（apply, prod）は、木の高さに比例する \(O(\log N)\) の時間で動作します。
  • 作業 2 では prod と apply を1回ずつ呼び出しますが、これも \(O(\log N)\) です。
  • クエリの回数は \(Q\) 回であるため、全体の計算量は \(O(Q \log N)\) となり、実行時間制限に十分間に合います。
• 空間計算量: \(O(N)\)
  • セグメント木の構築に必要なメモリは棚の数 \(N\) に対して線形（\(O(N)\)）です。

---

実装のポイント

• 0-indexed への変換 入力で与えられる棚の番号 \(l, r, p\) は 1-indexed（1から始まる番号）ですが、プログラム内部（セグメント木）では 0-indexed（0から始まる番号）として扱います。 そのため、入力を受け取った後に l-- や p-- を行う必要があります。

• 半開区間への変換 セグメント木のクエリ範囲は、一般的に半開区間 \([l, r)\)（\(l\) 以上 \(r\) 未満）で指定します。 問題文のクエリは閉区間 \([l, r]\)（\(l\) 以上 \(r\) 以下）なので、セグメント木に渡す右端のインデックスは \(r\) のまま（1減算しない）で渡すことで、半開区間 \( [l-1, r)\) として正しく処理できます。

  ソースコード

#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;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。