比较简单的 LIS 模板题。
回顾使用树状数组求解 LIS 问题的过程：用树状数组的下标表示 \(a\) 的值域，存储 \(f\) 的最大值。求解时在 \([1,a_i-1]\) 上取最大值，并更新到 \(a_i\) 对应的位置。
类似地，在本题中，询问前 \(R\) 个数且值不超过 \(X\) 的 LIS 长度，发现正好能用树状数组存储的信息解决。具体地，先把所有询问离线下来，并对 \(a\) 离散化，从前往后求 LIS。假设当前到了第 \(i\) 位，那么先用当前 \(a_i\) 更新树状数组，再解决所有 \(R=i\) 的询问，答案即为 \([1,X]\) 上的最大值（只需保证最大的一项即最后一项不超过 \(X\) 即可）。最后再一遍输出答案即可。
总时间复杂度 \(O( ( n + m )\log n)\)。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>using namespace std;struct Q
{int x,id;
};vector<Q> q[1000001];
int n,m,ans[1000001],a[1000001];
int f[1000001],tp;
int ls[1000001],tot;
int t[1000001];int lowbit( int x )
{return x & ( -x );
}void upd( int x , int y )
{for( int i = x ; i <= tot ; i += lowbit( i ) )t[i] = max( t[i] , y );return;
}int que( int x )
{int mx = 0;for( int i = x ; i >= 1 ; i -= lowbit( i ) )mx = max( mx , t[i] );return mx;
}bool cmp( Q x , Q y )
{return x.x < y.x;
}int main()
{int r,x;cin >> n >> m;for( int i = 1 ; i <= n ; i ++ )cin >> a[i],ls[++ tot] = a[i];for( int i = 1 ; i <= m ; i ++ ){cin >> r >> x;ls[++ tot] = x;q[r].push_back( { x , i } );}sort( ls + 1 , ls + tot + 1 );tot = unique( ls + 1 , ls + tot + 1 ) - ls - 1;for( int i = 1 ; i <= n ; i ++ ){a[i] = lower_bound( ls + 1 , ls + tot + 1 , a[i] ) - ls;for( auto &p : q[i] )p.x = lower_bound( ls + 1 , ls + tot + 1 , p.x ) - ls;}for( int i = 1 ; i <= n ; i ++ )sort( q[i].begin() , q[i].end() , cmp );for( int i = 1 ; i <= n ; i ++ ){ upd( a[i] , que( a[i] - 1 ) + 1 );for( auto p : q[i] )ans[p.id] = que( p.x );}for( int i = 1 ; i <= m ; i ++)cout << ans[i] << '\n';return 0;
}