令$f_{i}$表示以$i$为结尾的极长上升子序列个数，则有$f_{i}=sum_{j<i,a_{j}<a_{i},forall j<k<i,a_{k}
otin [a_{j},a_{i}]}f_{j}$
（初始状态为前缀最小值处$f_{i}=1$，最终答案为后缀最大值处的$f_{i}$之和）
暴力计算复杂度显然为$o(n^{2})$，无法通过
考虑分治计算，当递归到区间$[l,r]$时，需要求出仅考虑$[l,r]$内部的（包括转移的$j$）时的$f_{i}$
具体的，先递归$[l,mid]$，再求出$[l,mid]$对$(mid,r]$的影响，最后递归$(mid,r]$即可
第一步和第三步容易处理，接下来考虑第二步：
具体的，考虑将$a_{l},a_{l+1},…,a_{r}$从小到大排序后枚举，注意到此时左侧的数中，如果存在$x<y$且$a_{x}<a_{y}$，那么$x$一定不会被使用（因为之后右侧的$a_{i}>a_{y}$），也即可以维护一个单调栈
（关于这个单调栈，从栈底到栈顶位置单调递减、权值单调递增）
类似地，我们再对右侧维护一个单调栈，从栈底到栈顶位置和权值都单调递增，此时即查询比左边单调栈中比当前比右边单调栈栈顶（插入前，若为空则定义为0）大的位置的$f$之和，可以二分实现
由于需要排序和二分，总复杂度为$o(nlog^{2}n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define mod 998244353 5 int t,n,ans,a[N],id[N],stl[N],str[N],sum[N],f[N]; 6 bool cmp(int x,int y){ 7 return a[x]<a[y]; 8 } 9 void calc(int l,int r){ 10 if (l==r)return; 11 int mid=(l+r>>1); 12 calc(l,mid); 13 for(int i=l;i<=r;i++)id[i]=i; 14 sort(id+l,id+r+1,cmp); 15 stl[0]=str[0]=0; 16 for(int i=l;i<=r;i++){ 17 if (id[i]<=mid){ 18 while ((stl[0])&&(stl[stl[0]]<id[i]))stl[0]--; 19 stl[++stl[0]]=id[i]; 20 sum[stl[0]]=(sum[stl[0]-1]+f[id[i]])%mod; 21 } 22 else{ 23 while ((str[0])&&(str[str[0]]>id[i]))str[0]--; 24 int pos=lower_bound(stl+1,stl+stl[0]+1,str[str[0]],cmp)-stl; 25 str[++str[0]]=id[i]; 26 f[id[i]]=(f[id[i]]+(sum[stl[0]]-sum[pos-1]+mod)%mod)%mod; 27 } 28 } 29 calc(mid+1,r); 30 } 31 int main(){ 32 scanf("%d",&t); 33 while (t--){ 34 scanf("%d",&n); 35 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 36 int s=n+1; 37 for(int i=1;i<=n;i++){ 38 f[i]=(a[i]<s); 39 s=min(s,a[i]); 40 } 41 calc(1,n); 42 s=ans=0; 43 for(int i=n;i;i--){ 44 if (a[i]>s)ans=(ans+f[i])%mod; 45 s=max(s,a[i]); 46 } 47 printf("%d ",ans); 48 } 49 return 0; 50 }
View Code
You can also customize monitoring for certain apps, and it will immediately start capturing phone screen snapshots regularly.
Through the parental monitoring program, parents can pay attention to their children’s mobile phone activities and monitor WhatsApp messages more easily and conveniently. The application software runs silently in the background of the target device, recording conversation messages, emoticons, multimedia files, photos, and videos. It applies to every device running on Android and iOS systems.