以下内容参考2019年集训队论文《浅谈杨氏矩阵在信息学竞赛中的应用》
1.前置知识
杨表
标准杨表：一张网格图，满足以下条件——
1.设其有$m$行、第$i$行有$a_{i}$个格子（格子左对齐），则$a_{1}\ge a_{2}\ge ...\ge a_{m}$
2.每一个格子内有一个正整数，且每行每列都严格单调递增
3.记$n=\sum_{i=1}^{m}a_{i}$（即格子总数），所有格子内的正整数恰构成1到$n$的排列
半标准杨表：一张网格图，满足以下条件——
1.设其有$m$行、第$i$行有$a_{i}$个格子（格子左对齐），则$a_{1}\ge a_{2}\ge ...\ge a_{m}$
2.每一个格子内有一个正整数，且每行单调不下降、每列严格单调递增
（以下杨表默认均指半标准杨表）
记$\empty$为空杨表（即$m=0$时），$S_{i,j}$为杨表$S$第$i$行第$j$列的元素
插入和删除
行插入：对于一个杨表$S$，将$x\in Z^{+}$行插入$S$，过程如下：
1.找到第$i$行中第一个大于等于$x$的元素，将其与$x$交换（初始$i=1$）
2.将$i$增加1并重复第一步，直至第$i$行中没有大于等于$x$的元素，则将$x$加入到该行末尾
并记最终得到的杨表为$S\leftarrow x$
列插入：与行插入类似，将过程中的"行"将改为"列"即可，并记最终得到的杨表为$x\rightarrow S$
删除：对于一个杨表$S$，将第$i$行最后一个元素删除，过程如下：
1.找到第$i-1$行中最后一个小于等于$x$的的元素，将其与$x$交换（初始$x=S_{i,a_{i}}$）
2.将$i$减小1并重复第一步，直至$i=1$则结束
并记最终得到的杨表为$S-i$（其中$1\le i\le m$）
性质
性质1.1：对杨表执（行/列）插入或删除操作后仍是杨表
性质1.2：行插入和删除操作互为逆运算
关于这一性质，更完整的描述即以下两点——
1.假设在杨表$S$中行插入$x$后最终位于第$i$行，则$S=(S\leftarrow x)-i$
2.假设在杨表$S$中删除第$i$行后结束时的元素为$x$，则$(S-i)\leftarrow x=S$
性质1.3：$(S\leftarrow x)^{T}=x\rightarrow S^{T}$（其中$S$为标准杨表，$S^{T}$即将其转置）
性质1.4：$(x\rightarrow S)\leftarrow y=x\rightarrow(S\leftarrow y)$
关于这一性质的证明，参考论文的参考文献[10]
2.杨表和排列
对于一个排列$\{p_{i}\}$，构造其对应的杨表$S_{p}=((\empty\leftarrow p_{1})\leftarrow p_{2})\leftarrow...\leftarrow p_{n}$
在构造$S_{p}$的过程中，若插入$p_{x}$后$p_{x}$位于第$i$行第$j$列，则令$Q_{p}$第$i$行第$j$列的元素为$x$
性质2.1：$S_{p}$和$Q_{p}$均为标准杨表且两者形状相同（形状即每行元素个数相同）
性质2.2：$S_{\{p_{n},p_{n-1},...,p_{1}\}}=S_{p}^{T}$
关于这一性质的证明，根据性质1.3和1.4并归纳即可
性质2.3：对于任意两个形状相同的标准杨表$S_{1}$和$S_{2}$，恰存在一个排列$p_{i}$使得$(S_{1},S_{2})=(S_{p},Q_{p})$
关于这一性质的证明，根据性质1.2即可通过$(S_{1},S_{2})$构造排列$p_{i}$
性质2.4：$p_{i}$最长${\rm LIS}_{k}$子序列长度为$S_{p}$的前$k$列长度和
（其中${\rm LIS}_{k}$序列即最长上升子序列长度小于等于$k$的序列）
关于这一性质的证明，参考论文5.1的部分
3.杨表计数
定义序列$\{a_{1},a_{2},...,a_{m}\}\vdash n$当且仅当$a_{1}\ge a_{2}\ge ...\ge a_{m}$且$\sum_{i=1}^{m}a_{i}=n$
记$f_{\{a_{1},a_{2},...,a_{m}\}}$为第$i$行有$a_{i}$个格子的标准杨表个数，显然要有$a_{1}\ge a_{2}\ge ...\ge a_{m}$
性质3.1：$\sum_{a\vdash n}f_{a}^{2}=n!$
性质3.2：$f_{a}=\frac{n!}{\prod_{1\le i\le m,1\le j\le a_{i}}h_{a}(i,j)}$（其中$h_{a}(i,j)$表示$(i,j)$正右和正下方的格子数+1）
关于这一性质的证明，参考论文6.1的部分
类似地，记$g_{n,\{a_{1},a_{2},...,a_{m}\}}$为第$i$行有$a_{i}$个格子且值域为$[1,n]$的半标准杨表数
性质3.3：$g_{n,a}=\prod_{1\le i\le m,1\le j\le a_{i}}\frac{n+j-i}{h_{a}(i,j)}$
关于这一性质的证明，参考论文8.1和8.2的部分
4.其他
论文中还有以下几部分的内容：
(1)杨表和矩阵（第4部分）
(2)杨表和路径计数（6.2的部分和第7部分）
(3)复杂的杨表计数（第9部分）
（补充一下$q$的范围：$q\le 2\times 10^{5}$）
关于本题，将询问离线后按照$m$从小到大排序，并将所有数依次行插入杨表
暴力插入的复杂度为$o(n\log n)$，显然无法通过
对于杨表$S$，仅维护$S$的前$\sqrt{n}$行和$S^{T}$的前$\sqrt{n}$行（也即$S$的前$\sqrt{n}$列），注意到$S$中每一个格子的左上角格子必然是全的，因此这包含了$S$的所有元素（否则元素个数$>n$）
前者单次插入复杂度即$o(\sqrt{n}\log n)$，但后者仍难以处理
构造$S‘$也为所有数依次行插入杨表的结果，但将比较中的"大于等于"改为"小于"，那么$S‘$前$k$行的长度和即为最长${\rm LIS}_{k}$子序列，注意到这与$S^{T}$相同
换言之，有$S‘$和$S^{T}$形状相同，同时我们仅关心于形状而不关心于具体的数，即可以维护$S‘$代替$S^{T}$，同样单次插入复杂度为$o(\sqrt{n}\log n)$
关于查询，根据性质2.4即求前$k$列的长度和，注意到每次插入对杨表的形状只有一处变化，因此用树状数组维护即可，修改和询问复杂度均为$o(\log n)$
总复杂度为$o(n\sqrt{n}\log n+q\log n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 50005 4 #define K 250 5 struct Data{ 6 int l,k,id; 7 bool operator < (const Data &a)const{ 8 return l<a.l; 9 } 10 }q[N<<2]; 11 vector<int>v0[K],v1[K]; 12 int n,m,k,a[N],f[N],ans[N<<2]; 13 int lowbit(int k){ 14 return (k&(-k)); 15 } 16 void update(int k){ 17 while (k<=n){ 18 f[k]++; 19 k+=lowbit(k); 20 } 21 } 22 int query(int k){ 23 int ans=0; 24 while (k){ 25 ans+=f[k]; 26 k-=lowbit(k); 27 } 28 return ans; 29 } 30 void add0(int x){ 31 for(int i=1;i<=k;i++){ 32 if ((!v0[i].size())||(v0[i].back()<x)){ 33 v0[i].push_back(x); 34 if (v0[i].size()>k)update(v0[i].size()); 35 return; 36 } 37 swap(*lower_bound(v0[i].begin(),v0[i].end(),x),x); 38 } 39 } 40 void add1(int x){ 41 for(int i=1;i<=k;i++){ 42 if ((!v1[i].size())||(v1[i].back()<=x)){ 43 v1[i].push_back(x); 44 update(i); 45 return; 46 } 47 swap(*upper_bound(v1[i].begin(),v1[i].end(),x),x); 48 } 49 } 50 int main(){ 51 scanf("%d%d",&n,&m); 52 k=(int)sqrt(n); 53 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 54 for(int i=1;i<=m;i++){ 55 scanf("%d%d",&q[i].l,&q[i].k); 56 q[i].id=i; 57 } 58 sort(q+1,q+m+1); 59 for(int i=1,j=1;i<=n;i++){ 60 add0(a[i]),add1(-a[i]); 61 while ((j<=m)&&(q[j].l==i)){ 62 ans[q[j].id]=query(q[j].k); 63 j++; 64 } 65 } 66 for(int i=1;i<=m;i++)printf("%d\n",ans[i]); 67 }