[hdu6991]Increasing Subsequence

令$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)$，可以通过

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define mod 998244353
int t,n,ans,a[N],id[N],stl[N],str[N],sum[N],f[N];
bool cmp(int x,int y){
    return a[x]<a[y];
}
void calc(int l,int r){
    if (l==r)return;
    int mid=(l+r>>1);
    calc(l,mid);
    for(int i=l;i<=r;i++)id[i]=i;
    sort(id+l,id+r+1,cmp);
    stl[0]=str[0]=0;
    for(int i=l;i<=r;i++){
        if (id[i]<=mid){
            while ((stl[0])&&(stl[stl[0]]<id[i]))stl[0]--;
            stl[++stl[0]]=id[i];
            sum[stl[0]]=(sum[stl[0]-1]+f[id[i]])%mod;
        }
        else{
            while ((str[0])&&(str[str[0]]>id[i]))str[0]--;
            int pos=lower_bound(stl+1,stl+stl[0]+1,str[str[0]],cmp)-stl;
            str[++str[0]]=id[i];
            f[id[i]]=(f[id[i]]+(sum[stl[0]]-sum[pos-1]+mod)%mod)%mod;
        }
    }
    calc(mid+1,r);
}
int main(){
    scanf("%d",&t);
    while (t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        int s=n+1;
        for(int i=1;i<=n;i++){
            f[i]=(a[i]<s);
            s=min(s,a[i]);
        }
        calc(1,n);
        s=ans=0;
        for(int i=n;i;i--){
            if (a[i]>s)ans=(ans+f[i])%mod;
            s=max(s,a[i]);
        }
        printf("%d
",ans);
    }
    return 0;
}