把询问离线之后就变成了一个二分求最长上升子序列的问题，参考导弹拦截
求上升子序列
用一个数组f[i]记录 目前长度为i的结尾最小值
dp[i]记录以当前第i位结尾的最长上升子序列
f[i]随着i的增加单调递增，可以二分找位置
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
struct nd {
int r, x, id;
bool operator< (const nd& b) const {
return r < b.r;
}
};
const int inf = 1e18;
const int N = 2e5 + 10;
int dp[N], f[N], ans[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n+1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
f[i] = inf;
}
vector<nd> b(q);
for (int i = 0; i < q; i++) {
cin >> b[i].r >> b[i].x;
b[i].id = i + 1;
}
sort(b.begin(),b.end());
auto fd = [&] (int cur, int v, bool flg) {
int L = 1, R = cur;
int res = 0;
while (L <= R) {
int mid = L + R >> 1;
if (flg ? f[mid] < v : f[mid] <= v) {
res = max(res,mid);
L = mid + 1;
} else {
R = mid - 1;
}
}
return res;
};
for (int i = 0, j = 1; i < q; i++) {
while (j <= b[i].r) {
int val = fd(j-1,a[j],1);
dp[j] = val + 1;
f[val+1] = a[j];
// cout << j << " " << val << " " << a[j] << endl;
j++;
}
// cout << b[i].r << " " << j << endl;
ans[b[i].id] = fd(b[i].r,b[i].x,0);
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << '\n';
}
return 0;
}