概要

\(D_i = B_i - A_i\) とおくと、求める値は \(\sum_i \max(0, D_i)\) です。
各クエリは区間 \([L,R]\) に対する \(D_i\) の加算または減算になるので、「区間加算」と「正の部分の総和」を高速に管理します。

考察

まず、倉庫 \(i\) の不足分は

\(\max(0, B_i - A_i)\)

です。そこで

\(D_i = B_i - A_i\)

と定義すると、答えは

\(\sum_i \max(0, D_i)\)

になります。

クエリは次のように言い換えられます。

• \(T=1\)：\(B_i\) が \(X\) 増える
  \(\Rightarrow D_i\) が \(X\) 増える
• \(T=2\)：\(A_i\) が \(X\) 増える
  \(\Rightarrow D_i\) が \(X\) 減る

つまり、問題は次の操作を処理することになります。

• 区間 \([L,R]\) の \(D_i\) に同じ値を加算する
• 各操作後に \(\sum_i \max(0,D_i)\) を出力する

素朴に毎回区間内の要素をすべて更新し、全体の答えを計算すると \(O(NQ)\) になり、最大で \(5 \times 10^4 \times 5 \times 10^4\) となるため間に合いません。

また、単に区間ごとの「正の部分の総和」だけを持っていても、区間加算後の値は分かりません。
例えば、現在の正の部分の総和が同じ \(5\) でも、

• \([5, -100]\) に \(-3\) を加えると答えは \(2\)
• \([2, 3]\) に \(-3\) を加えると答えは \(0\)

となり、値の分布が必要になります。

そこで、平方分割を使います。
各ブロック内の \(D_i\) をソートして持っておけば、「どの要素が正になるか」を二分探索で求められます。

アルゴリズム

\(D_i = B_i - A_i\) を配列として管理します。

配列を長さ \(K\) 程度のブロックに分割します。
このコードでは \(K=256\) としています。

各ブロックについて、次の情報を持ちます。

• lazy
  ブロック全体に一様に加算された値
• ord
  各要素の値 \(v_i\) と位置 pos の組を、\(v_i\) の昇順に並べたもの
• pref
ord の値の累積和
• ans
  そのブロック内の \(\sum \max(0,D_i)\)
• idx
  正になる要素が始まる位置

ここで、実際の値は

\(D_i = v_i + lazy\)

です。

したがって、\(D_i > 0\) となる条件は

\(v_i + lazy > 0\)

すなわち

\(v_i > -lazy\)

です。

ord は \(v_i\) の昇順に並んでいるので、\(v_i > -lazy\) となる最初の位置を idx とすれば、正になる要素は idx 以降の suffix です。

ブロックの答えは

\(\sum_{k=idx}^{sz-1} (ord[k].v + lazy)\)

なので、累積和 pref を使って

\(\text{ans} = pref[sz] - pref[idx] + (sz - idx) \times lazy\)

と計算できます。

例えば、ブロック内の値が

\([-4, -1, 2, 5]\)

で、lazy = 1 なら、実際の値は

\([-3, 0, 3, 6]\)

です。
正になるのは \(2,5\) の部分なので、答えは

\((2+5) + 2 \times 1 = 9\)

です。

ブロック全体に加算する場合

ブロック全体に \(\delta\) を加える場合、各要素を直接更新する必要はありません。

lazy += delta

とするだけでよいです。

その後、条件

\(v_i > -lazy\)

を満たす最初の位置を二分探索で求め、ans を更新します。

ブロックの一部に加算する場合

ブロックの一部だけに \(\delta\) を加える場合は、該当する要素だけ \(v_i\) を更新する必要があります。

このとき、ブロックサイズは高々 \(K\) なので、ブロック内を走査して更新します。

ただし、更新後も ord を昇順に保つ必要があります。

コードでは次のようにしています。

1. ord を走査する
2. 更新対象の要素を取り出し、値に \(\delta\) を加えて changed に入れる
3. 更新対象でない要素はそのまま残す
4. changed と未更新要素列をマージして、新しい ord を作る
5. pref, idx, ans を作り直す

changed は、元々ソート済みの ord から順番に取り出したものに同じ \(\delta\) を加えているため、これもソート済みです。
そのため、全体を再ソートせずにマージだけで済みます。

クエリ処理

各クエリについて、まず加算値 \(\delta\) を決めます。

• \(T=1\) のとき \(\delta = X\)
• \(T=2\) のとき \(\delta = -X\)

区間 \([L,R]\) に対して、

• 完全に含まれるブロックには「ブロック全体加算」
• 端の一部だけ含まれるブロックには「ブロック一部加算」

を行います。

全体の答え total は、各ブロックの ans の合計として持っておきます。
ブロックを更新するときは、更新前後の ans の差分だけ total に反映します。

計算量

ブロックサイズを \(K\) とします。

• 初期構築: \(O(N \log K)\)
• 1 クエリあたり:
  • 端の部分ブロックの処理: \(O(K)\)
  • 完全に含まれるブロックの処理: \(O\left(\frac{N}{K} \log K\right)\)

したがって、全体では

• 時間計算量: \(O\left(N \log K + Q\left(K + \frac{N}{K}\log K\right)\right)\)
• 空間計算量: \(O(N)\)

この実装では \(K=256\) としており、\(N,Q \leq 5 \times 10^4\) に対して十分高速です。

実装のポイント

• \(D_i = B_i - A_i\) だけを管理すればよく、\(A_i,B_i\) を個別に持つ必要はありません。

• \(T=2\) のときは \(D_i\) に \(-X\) を加える点に注意します。

• 答えは最大で \(10^{18}\) 以下なので、long long を使います。

• 入力は \(1\)-indexed ですが、実装では \(0\)-indexed に変換しています。

• 部分更新のときも lazy はそのままにし、保存している \(v_i\) だけを更新します。
  実際の値は常に \(v_i + lazy\) と考えます。

• ブロックの答えが変化したら、total += 新しいans - 古いans として全体の答えを更新します。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

class FastScanner {
    static constexpr int BUFSIZE = 1 << 20;
    int idx = 0, size = 0;
    char buf[BUFSIZE];

    inline char getChar() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return 0;
        }
        return buf[idx++];
    }

public:
    template <class T>
    bool read(T &out) {
        char c = getChar();
        if (!c) return false;

        while (c != '-' && (c < '0' || c > '9')) {
            c = getChar();
            if (!c) return false;
        }

        T sign = 1;
        if (c == '-') {
            sign = -1;
            c = getChar();
        }

        T num = 0;
        while (c >= '0' && c <= '9') {
            num = num * 10 + (c - '0');
            c = getChar();
        }

        out = num * sign;
        return true;
    }
};

inline void append_ll(string &s, ll x) {
    if (x == 0) {
        s.push_back('0');
        s.push_back('\n');
        return;
    }

    if (x < 0) {
        s.push_back('-');
        x = -x;
    }

    char buf[32];
    int n = 0;
    while (x > 0) {
        buf[n++] = char('0' + x % 10);
        x /= 10;
    }
    while (n--) s.push_back(buf[n]);
    s.push_back('\n');
}

struct Item {
    ll v;
    int pos;
};

struct Block {
    int l, r, sz;
    ll lazy = 0;
    ll ans = 0;
    int idx = 0;

    vector<Item> ord;
    vector<Item> tmp;
    vector<Item> changed;
    vector<ll> pref;

    void build(int L, int R, const vector<ll> &d) {
        l = L;
        r = R;
        sz = r - l + 1;
        lazy = 0;

        ord.clear();
        ord.reserve(sz);
        tmp.reserve(sz);
        changed.reserve(sz);
        pref.assign(sz + 1, 0);

        for (int i = l; i <= r; i++) {
            ord.push_back({d[i], i});
        }

        sort(ord.begin(), ord.end(), [](const Item &a, const Item &b) {
            return a.v < b.v;
        });

        rebuild_info();
    }

    void rebuild_info() {
        pref[0] = 0;
        idx = sz;
        ll th = -lazy;

        for (int i = 0; i < sz; i++) {
            if (idx == sz && ord[i].v > th) idx = i;
            pref[i + 1] = pref[i] + ord[i].v;
        }

        ans = pref[sz] - pref[idx] + (ll)(sz - idx) * lazy;
    }

    void add_all(ll delta, ll &total) {
        ll old = ans;
        lazy += delta;
        ll th = -lazy;

        if (delta > 0) {
            if (idx != 0) {
                if (ord[0].v > th) {
                    idx = 0;
                } else if (ord[idx - 1].v <= th) {
                    // unchanged
                } else {
                    int lo = 0, hi = idx;
                    while (lo < hi) {
                        int mid = (lo + hi) >> 1;
                        if (ord[mid].v <= th) lo = mid + 1;
                        else hi = mid;
                    }
                    idx = lo;
                }
            }
        } else {
            if (idx != sz) {
                if (ord[sz - 1].v <= th) {
                    idx = sz;
                } else if (ord[idx].v > th) {
                    // unchanged
                } else {
                    int lo = idx + 1, hi = sz;
                    while (lo < hi) {
                        int mid = (lo + hi) >> 1;
                        if (ord[mid].v <= th) lo = mid + 1;
                        else hi = mid;
                    }
                    idx = lo;
                }
            }
        }

        ans = pref[sz] - pref[idx] + (ll)(sz - idx) * lazy;
        total += ans - old;
    }

    void add_part(int ql, int qr, ll delta, ll &total) {
        ll old = ans;

        changed.clear();

        for (const auto &it : ord) {
            int p = it.pos;
            if (ql <= p && p <= qr) {
                changed.push_back({it.v + delta, p});
            }
        }

        tmp.clear();
        pref[0] = 0;

        int pidx = 0;
        int cidx = 0;
        int k = (int)changed.size();
        int cnt = 0;
        int newIdx = sz;
        ll th = -lazy;

        while (cnt < sz) {
            while (pidx < sz) {
                int p = ord[pidx].pos;
                if (ql <= p && p <= qr) ++pidx;
                else break;
            }

            if (cidx < k && (pidx >= sz || changed[cidx].v <= ord[pidx].v)) {
                const Item &it = changed[cidx++];
                tmp.push_back(it);
                if (newIdx == sz && it.v > th) newIdx = cnt;
                pref[cnt + 1] = pref[cnt] + it.v;
            } else {
                const Item &it = ord[pidx++];
                tmp.push_back(it);
                if (newIdx == sz && it.v > th) newIdx = cnt;
                pref[cnt + 1] = pref[cnt] + it.v;
            }

            ++cnt;
        }

        ord.swap(tmp);
        idx = newIdx;
        ans = pref[sz] - pref[idx] + (ll)(sz - idx) * lazy;
        total += ans - old;
    }
};

int main() {
    FastScanner fs;

    int N, Q;
    fs.read(N);
    fs.read(Q);

    vector<ll> d(N);
    for (int i = 0; i < N; i++) {
        ll A, B;
        fs.read(A);
        fs.read(B);
        d[i] = B - A;
    }

    static constexpr int BS = 256;
    int M = (N + BS - 1) / BS;

    vector<Block> blocks(M);
    ll total = 0;

    for (int b = 0; b < M; b++) {
        int L = b * BS;
        int R = min(N, (b + 1) * BS) - 1;
        blocks[b].build(L, R, d);
        total += blocks[b].ans;
    }

    string output;
    output.reserve((size_t)Q * 22);

    for (int qi = 0; qi < Q; qi++) {
        int T, L, R;
        ll X;
        fs.read(T);
        fs.read(L);
        fs.read(R);
        fs.read(X);

        --L;
        --R;

        ll delta = (T == 1 ? X : -X);

        int bl = L / BS;
        int br = R / BS;

        if (bl == br) {
            if (L == blocks[bl].l && R == blocks[bl].r) {
                blocks[bl].add_all(delta, total);
            } else {
                blocks[bl].add_part(L, R, delta, total);
            }
        } else {
            if (L == blocks[bl].l) {
                blocks[bl].add_all(delta, total);
            } else {
                blocks[bl].add_part(L, blocks[bl].r, delta, total);
            }

            for (int b = bl + 1; b <= br - 1; b++) {
                blocks[b].add_all(delta, total);
            }

            if (R == blocks[br].r) {
                blocks[br].add_all(delta, total);
            } else {
                blocks[br].add_part(blocks[br].l, R, delta, total);
            }
        }

        append_ll(output, total);
    }

    fwrite(output.data(), 1, output.size(), stdout);
    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。