- 给定一个长度为(n)的序列。
- (q)次询问，每次求长为(m)的前缀中，最长的满足(LIS)长度不超过(k)的子序列长度。
- (nle5 imes10^4,qle2 imes10^5)
(k-LIS)问题——杨表的典型应用
关于杨表可见：杨表的构造与基本性质。
首先离线，就只要考虑一个一个把排列中的元素插入杨表。显然题目询问的就是(k-LIS)长度，这玩意儿就是杨表的前(k)列长度之和。
然而，若要直接维护整张杨表，单次插入的最劣复杂度是(O(nlogn))的。
考虑杨表逐行列数不增的性质，则显然也有逐列行数不增。
因此，假设一个数执行插入操作后最终插入到((x,y))的位置，则(x,y)中至少有一个小于等于(sqrt n)。
所以我们维护好运算符取反后杨表的前(sqrt n)行（与原杨表形状上行列交换，因此对应长度就是原杨表前(sqrt n)列的长度），以及原杨表的前(sqrt n)行（求大于(sqrt n)的列长度，必然是完整的）。
一次插入算法只会影响一列的长度，视作单点修改，可以直接用树状数组维护。
代码：(O(nsqrt nlogn+qlogn))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 50000
#define M 200000
#define S 250
using namespace std;
int n,Qt,a[N+5],ans[M+5];struct node {int p,k;};vector<node> s[N+5];
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('
');}
}using namespace FastIO;
struct TreeArray
{
int a[N+5];I void U(RI x) {W(x<=n) ++a[x],x+=x&-x;}//单点修改
I int Q(RI x,RI t=0) {W(x) t+=a[x],x-=x&-x;return t;}//前缀询问
}T;
namespace Y1//原杨表（每行严格递增）
{
int c[S+5],a[S+5][N+5];I void A(RI v)
{
for(RI i=1,p;i<=S;++i)//只维护前S行
{
if(!c[i]||a[i][c[i]]<v) return (void)(a[i][++c[i]]=v,c[i]>S&&(T.U(c[i]),0));//若列数大于S则计算贡献
p=lower_bound(a[i]+1,a[i]+c[i]+1,v)-a[i],swap(v,a[i][p]);//找到最小的大于等于它的数交换
}
}
}
namespace Y2//运算符取反后杨表（为了使用lower_bound，事先将插入值取负，因此每行非严格递增）
{
int c[S+5],a[S+5][N+5];I void A(RI v)
{
for(RI i=1,p;i<=S;++i)//只维护前S行
{
if(!c[i]||a[i][c[i]]<=v) return (void)(a[i][++c[i]]=v,T.U(i),0);//行长度对应原杨表列长度
p=upper_bound(a[i]+1,a[i]+c[i]+1,v)-a[i],swap(v,a[i][p]);//找到最小的大于它的数交换
}
}
}
int main()
{
RI i;for(read(n,Qt),i=1;i<=n;++i) read(a[i]);
RI x,y;for(i=1;i<=Qt;++i) read(x,y),s[x].push_back((node){i,y});//离线
vector<node>::iterator it;for(i=1;i<=n;++i)//把排列中的数一个一个插入杨表
for(Y1::A(a[i]),Y2::A(-a[i]),it=s[i].begin();it!=s[i].end();++it) ans[it->p]=T.Q(it->k);//处理当前前缀上的询问
for(i=1;i<=Qt;++i) writeln(ans[i]);return clear(),0;
}