LIS（最長単調増加部分列）の長さを求める際に典型的に用いられる以下の動的計画法を考えます。（この動的計画法の遷移やその正当性に関する解説はここでは省略します。）

• \(i=1,2\dots,N\) の順に \(A_i\) を見てゆき、以下の DP テーブルを in-place に更新する。
  • \(\mathrm{dp}_j\ (1\leq j\leq N)=\)（今までに見た要素の中から取り出せる長さ \(j\) の単調増加部分列における、部分列の末尾の要素の最小値。ただし、そのような部分列が存在しない場合は \(\infty\)）

上記の動的計画法の定義を考えれば、クエリ \(k\) の答えは以下の値に等しいことがわかります。

• \(i=R_k\) まで見た段階での DP テーブルにおいて、\(\mathrm{dp}_j \leq X_k\) を満たす最大の \(j\)

よって、上記の動的計画法を行いながら、その過程の各 \(i\) において、\(i=R_k\) を満たす全てのクエリ \(k\) の答えをそれぞれ二分探索で求めればよいです。

全体の計算量は \(O((N+Q)\log N)\) です。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9 + 100;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int &i: a) cin >> i;
    vector<vector<pair<int, int>>> qs(n);
    for (int i = 0; i < q; i++) {
        int r, x;
        cin >> r >> x;
        qs[--r].emplace_back(i, x);
    }
    vector<int> ans(q);
    vector<int> dp(n, inf);
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(dp.begin(), dp.end(), a[i]);
        *it = a[i];
        for (auto [id, x]: qs[i]) {
            ans[id] = upper_bound(dp.begin(), dp.end(), x) - dp.begin();
        }
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }
}