愚直な解法として、各クエリで与えられた最初のレート \(X\) をもとに \(N\) 回のコンテストを \(1\) 回ずつ順番にシミュレーションするという解法が考えられます。この方法の時間計算量は \(O(NQ)\) になり、本問題の制約下では十分高速ではありません。

ここで、各クエリでコンテストをシミュレーションするのではなく、クエリを答える前に前もって \(X=1,2,3,\ldots,5 \times 10^{5}\) の場合の答えを求めておいて各クエリでは事前に計算した値を答えるという方法を考えます。

元々の愚直な解法とは違い、\(1\) 回ずつコンテストを行い、\(X=1,2,3,\ldots,5 \times 10^{5}\) であった場合の現在のレートを求めていきます。ここで以下のような動的計画法を考えます。

\(dp[i][j]=(\) 初めにレートが \(j\) であったときに\(i\) 回のコンテスト後のレート \()\) と定義します。最初、\(j=1,2,\ldots,5 \times 10^{5} \) について\(dp[0][j]=j\) で初期化し、遷移は以下のようになっています。

\(dp[i][j]=\left \{ \begin{array}{ll} dp_[i-1][j]+1 & (L_i \leq dp[i-1][j] \leq R_i) \\ dp_[i-1][j] & (dp[i-1][j] <L_i \lor dp[i-1][j] >R_i) \end{array} \right\} \)

最終的に、計算したいものは \(dp[N][*]\) だけですが、このまま愚直に \(dp\) を求めても高速ではありません。この配列 の特徴から高速化することを考えます。

まずこの\(dp\) 配列の特徴として、\(dp[i][j] \leq dp[i][j+1]\) が必ず成り立ちます。レートは \(1\) ずつしか変動しないため、最初のレートが \(X\) のときは \(X+1\) であった場合のレートと等しくなることはあっても等しくなったらそれ以降はレートは必ず等しくなりレートの初期値の大小とコンテスト後のレートの大小が入れ替わることはないです。

つまり、先ほどの \(dp\) の遷移ではある \(l,r\) について、 \(l \leq j \leq r\) の場合、 \(dp[i][j]=dp[i-1][j]+1\) になり、それ以外は \(dp[i][j]=dp[i-1][j]\) になるというように言い換えることが可能です。

ここで、この\(dp\) をいわゆるin-place化(インラインDP)することを考えます。\(dp[i][j]\) における\(i\) を省略し、\(D[j]\) を随時更新していくというような形を考えます。このとき、\(D\) に対する操作は \(D\) の要素の取得と区間加算です。よって、区間加算遅延セグメント木を用いることで \(dp[N]\) を求めることができます。遅延セグメント木の要素取得は \(O(\log X)\) で、二分探索に \(O(\log X)\) 、これを \(N\) 回のコンテスト分行うため、全体で \(O(X+N (\log X)^2 +Q \log X)\) 時間で解くことが可能です。

遅延セグメント木を区間最大値区間加算の両方ともができるものにすることによって、\(l,r\) を求める際にセグメント木上の二分探索(ACL では max_right や min_left) を用いることで時間計算量 \(O(X+N \log X+Q \log X)\) で解くことができます。 実装例はこの解法の実装になっています。

実装例(C++):

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

int op(int a, int b) { return max(a, b); }
int e() { return -1e9; }
int mapping(int f, int x) { return f + x; }
int composition(int f, int g) { return f + g; }
int id() { return 0; }

int main() {
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    for (int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i];
    }
    vector<int> rate(500000, 0);
    iota(rate.begin(), rate.end(), 1);
    atcoder::lazy_segtree<int, op, e, int, mapping, composition, id> seg(rate);
    for (int i = 0; i < n; ++i) {
        auto L = seg.max_right(0, [&](int x) { return x < l[i]; });
        auto R = seg.max_right(0, [&](int x) { return x <= r[i]; });
        seg.apply(L, R, 1);
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int x;
        cin >> x;
        x--;
        cout << seg.get(x) << "\n";
    }
}