だいたい公式解説と同じです。

fenwick-treeといもす法を使うと、以下のようなクエリが \(O(\log N)\) でできます。

• \(a[l], a[l+1], ... , a[r - 1]\) に \(x\) を加える

• \(a[x]\) を出力

fenwick-treeでは、一点add、区間sumが出来ますが、上の1つ目のクエリを「 \(a[l]\) に \(x\) を加えて \(a[r]\) に \(-x\) を加える」、2つ目のクエリを「\(a[0],a[1], ..., a[x]\) の総和を出力」とすることで上記クエリを実現できます。

fenwick-tree上でも二分探索が愚直だと \(O((\log N)^2)\) のところを \(O(\log N)\) でできます (が、C++などの高速な言語だと愚直でも通りますし、実装が悪いのか、そんなに実行時間変わりませんでした)。

以下の計算量は \(X = 500000\) としています。

実装例 ( \(O((X+N+Q)\log X)\) , C++, 493 ms)

https://atcoder.jp/contests/abc389/submissions/61841120

#include <bits/stdc++.h>
using namespace std;
int N = 500010;

template <class T> struct fenwick_tree {
    int n;
    vector<T> a;
    fenwick_tree(int m) : n(m), a(m + 1, 0) {}
    void add(int x, T y) {
        x ++;
        while(x <= n) {
            a[x] += y;
            x += x & -x;
        }
    }
    T sum(int x) {
        T r = 0;
        while(x > 0) {
            r += a[x];
            x -= x & -x;
        }
        return r;
    }
    T sum(int x, int y) { // [x, y), 0-indexed
        return sum(y) - sum(x);
    }
    int lower_bound(T x) {
        int id = 0;
        for(int i = __lg(n); i >= 0; i --) {
            if((id | (1 << i)) > n) continue;
            if(a[id | (1 << i)] < x) {
                x -= a[id | (1 << i)];
                id |= (1 << i);
            }
        }
        return id;
    }
};

int main() {
    int n;
    cin >> n;
    fenwick_tree<int> fw(N);
    for(int i = 1; i < N; i ++) fw.add(i, 1);
    for(int i = 0; i < n; i ++) {
        int a, b;
        cin >> a >> b;
        int id1 = fw.lower_bound(a);
        if(fw.sum(0, N) > b + 1) {
            int id2 = fw.lower_bound(b + 1);
            fw.add(id1, 1);
            fw.add(id2, -1);
        } else {
            fw.add(id1, 1);
        }
    }
    int q; cin >> q;
    for(int i = 0; i < q; i ++) {
        int x; cin >> x;
        cout << fw.sum(0, x + 1) << endl;
    }
    return 0;
}

実装例 (27行目～37行目の部分のみ変更して記載, \(O((X + Q)\log X + N (\log X)^2)\) , C++, 555 ms)

https://atcoder.jp/contests/abc389/submissions/61841100

    int lower_bound(T x) {
        int le = 0, ri = N;
        while(ri - le > 1) {
            int mid = (ri + le) / 2;
            if(sum(0, mid) >= x) {
                ri = mid;
            } else {
                le = mid;
            }
        }
        return le;
    }