次のような問題を考えます。

\(N\) 基の電波塔が建てられています。\(i\) 番目の電波塔は座標 \(X _ i\) に建てられており、強度 \(B _ i\) です。 それぞれの電波塔は区間 \(\lbrack X _ i-B _ i,X _ i+B _ i\rbrack\) に含まれる座標に電波強度 \(1\) を届けます。\(Q\) 個の区間 \(\lbrack L _ j,R _ j\rbrack\) について、含まれる整数座標 \(p\) に対する \(f(p)\) の最大値を求めてください。

これは、imos 法と呼ばれるテクニックを用いて解くことができます。

imos 法では、いくつかの長さ \(N\) の列に対して、

• 合計してから累積和をとったもの
• 累積和をとってから合計したもの

が等しいことを利用して、合計を求めるのが簡単な（\(0\) でない要素が少ない）列に変換することになります。

この問題では、累積和を \(2\) 回とることで目的の列になるようなものを考えることで（あるいは目的の列に対して階差を \(2\) 回とることで）、\(0\) でない要素が \(3\) つの列をいくつか合計する処理に帰着させることができます。

クエリで聞かれる \(p\) の範囲は \(0\) 以上 \(2\times10 ^ 5\) 以下なので、それぞれに対する電波強度を求められれば、セグメント木などを用いてこの問題を解くことができます。

\(p\) の範囲の長さを \(M\) として、時間計算量は \(O(N+M+Q\log M)\) 、空間計算量は \(O(M)\) などになります。

実装例は以下のようになります。 求める範囲の外に対して操作を行いたい場合があることに注意してください（範囲を広げたり、適切に端の処理を行ったりする必要があります）。

#include <iostream>
#include <vector>
#include <numeric>
#include <atcoder/segtree>

int main() {
    using namespace std;
    int N, Q;
    cin >> N >> Q;
    constexpr int road_length = 200000;
    vector<long> signal_strength(road_length + 1);

    for (int i = 0; i < N; ++i) {
        int X, B;
        cin >> X >> B;
        signal_strength[0] += max(0, B - X);
        signal_strength[max(1, X - B + 1)] += 1;
        if (X < road_length) {
            signal_strength[X + 1] -= 2;
        }
        if (B + X < road_length) {
            signal_strength[B + X + 1] += 1;
        }
    }

    // 2 回累積和をとる
    inclusive_scan(signal_strength.begin() + 1, signal_strength.end(), signal_strength.begin() + 1);
    inclusive_scan(signal_strength.begin(), signal_strength.end(), signal_strength.begin());

    // 区間最大値を求めるセグメント木
    atcoder::segtree<long, [](long a, long b){return max(a, b);}, []{return 0L;}> segment_tree(signal_strength);

    for (int i = 0; i < Q; ++i) {
        int L, R;
        cin >> L >> R;
        cout << segment_tree.prod(L, R + 1) << endl; // クエリに答える
    }
    return 0;
}

from atcoder.segtree import SegTree


N, Q = map(int, input().split())

road_length = 200000
signal_strength = [0 for _ in range(road_length + 1)]

for i in range(N):
    X, B = map(int, input().split())
    signal_strength[0] += max(0, B - X)
    signal_strength[max(1, X - B + 1)] += 1
    if X < road_length:
        signal_strength[X + 1] -= 2
    if X + B < road_length:
        signal_strength[B + X + 1] += 1

# 2 回累積和をとる
for i in range(2, road_length + 1):
    signal_strength[i] += signal_strength[i - 1]
for i in range(1, road_length + 1):
    signal_strength[i] += signal_strength[i - 1]

# 区間最大値を求めるセグメント木

segment_tree = SegTree(max, 0, signal_strength)

for i in range(Q):
    L, R = map(int, input().split())
    print(segment_tree.prod(L, R + 1)) # クエリに答える