ギブ and テイク [yukicoder No.728] - はまやんはまやんはまやん

解法

まずは愚直解法を書こう。

ll ans = 0;
rep(j, 0, N) rep(i, 0, j) if (A[j] <= A[i] + R[i] and A[j] - L[j] <= A[i]) ans++;
cout << ans << endl;

A[j]≦A[i]+R[i]かA[j]-L[j]≦A[i]をうまく扱いたい。
まず、A[j]-L[j]≦A[i]はiを[0,j)でイテレートしているが、条件を満たすかどうかは単調であるため、
A[j]-L[j]≦A[k]を満たす最小のkが見つかれば、[k,j)でイテレートすれば良いことがわかる。
これで

ll ans = 0;
rep(j, 0, N) {
    int k = lower_bound(A, A + N, A[j] - L[j]) - A;
    rep(i, k, j) if (A[j] <= A[i] + R[i]) ans++;
}
cout << ans << endl;

ここまでくる。
あとは、A[j]≦A[i]+R[i]をlogNでやれればACできる。
(i, A[i]+R[i])に点があると考えると、x座標が[k, j)でy座標が[A[j], inf)にある点の数が求めるべき数になる。
これはデータ構造持ってたので貼ると答えられる。
貼った解法

int N, A[301010], L[301010], R[301010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> L[i] >> R[i];

    vector<vector<pair<int,int>>> idx(N);
    rep(i, 0, N) idx[i].push_back({ A[i] + R[i], 1 });
    StaticHealthy2DSegTree st;
    st.init(idx);

    ll ans = 0;
    rep(j, 0, N) {
        int i = lower_bound(A, A + N, A[j] - L[j]) - A;
        ans += st.get(i, j, A[j], inf*2);
    }
    cout << ans << endl;
}

BITを使った解法もある
方針は同じなのだが、x座標が[i,j)である範囲を取ってきていたのをx座標が[0,j)-x座標が[0,i)と考えて解く。
あと、y座標も予め座圧しておく。
x座標を順番に見て、BITを更新、BITから取得としていくことで、
x座標が[0,j)のときのBITを対象としてクエリがさばける。
順番にはできないので、クエリ化して解こう。
下の解法ではクエリ化して+,-を付けていくが、特にx座標が[0,j)-x座標が[0,i)とせずに結局すべて足し合わせるので、
総和を取れば答え。

int N, A[301010], L[301010], R[301010];
vector<int> z;
vector<pair<int, int>> query[301010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> L[i] >> R[i];

    rep(i, 0, N) z.push_back(A[i] + R[i]);
    rep(i, 0, N) z.push_back(A[i]);
    sort(all(z));
    z.erase(unique(all(z)), z.end());

    int m = z.size();
    BIT<int> bit(m);

    rep(j, 0, N) {
        int i = lower_bound(A, A + N, A[j] - L[j]) - A;
        
        // [i,j) -> (i-1,j-1]
        if (0 <= i - 1) query[i - 1].push_back({ A[j], -1 });
        if (0 <= j - 1) query[j - 1].push_back({ A[j], 1 });
    }

    ll ans = 0;
    rep(j, 0, N) {
        int i = lower_bound(all(z), A[j] + R[j]) - z.begin();
        bit.add(i, 1);
        fore(q, query[j]) {
            int i = lower_bound(all(z), q.first) - z.begin();
            ans += bit.get(i, m) * q.second;
        }
    }
    cout << ans << endl;
}