题目大意
给一个排列，问有多少个极大上升子序列，极大是指这个序列不能是其他上升子序列的子序列。
题解
令\(f_i\)表示以\(i\)结尾的子序列个数，那么转移的话枚举前面比它小的位置，转移的话这两个位置之间不能有这两个值之间的数。
考虑分治算这个东西，我们分治\((l,mid)\)和\((mid+1,r)\)两个区间，计算两个区间之间的贡献，那么我们先去归并这两个序列，在归并的过程中，对于右边序列，我们维护一个位置单调上升的单调栈，左边维护单调下降的单调栈，这样，在右边序列，我们可以利用单调栈找到它前面比它小的最大的元素， 左边的单调栈维护的是合法转移的位置，最后再左边二分出比那个最大的元素大的位置，转移过来即可。
代码
#include<bits/stdc++.h>
#define N 200009
using namespace std;
typedef long long ll;
const int mod=998244353;
int a[N],n,b[N],c[N],pos[N];
int st[N],st1[N],dp[N],dp1[N];
inline ll rd(){
ll x=0;char c=getchar();bool f=0;
while(!isdigit(c)){if(c==‘-‘)f=1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f?-x:x;
}
inline void MOD(int &x){x=x>=mod?x-mod:x;}
inline void solve(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
solve(l,mid);
for(int i=l;i<=mid;++i){
b[i]=a[i];
}
for(int i=mid+1;i<=r;++i){
c[i]=a[i];
}
sort(b+l,b+mid+1);
sort(c+mid+1,c+r+1);
int s1=l,s2=mid+1;
int top1=0,top=0;
while(s1<=mid&&s2<=r){
if(b[s1]<c[s2]){
while(top1&&pos[st1[top1]]<pos[b[s1]])top1--;
st1[++top1]=b[s1];
MOD(dp1[top1]=dp1[top1-1]+dp[pos[b[s1]]]);
s1++;
}
else{
while(top&&pos[st[top]]>pos[c[s2]])top--;
int now=0;
if(top)now=st[top];
st[++top]=c[s2];
int x=max(0ll,upper_bound(st1+1,st1+top1+1,now)-st1-1);
MOD(dp[pos[c[s2]]]+=(dp1[top1]-dp1[x]+mod)%mod);
s2++;
}
}
while(s2<=r){
while(top&&pos[st[top]]>pos[c[s2]])top--;
int now=0;
if(top)now=st[top];
st[++top]=c[s2];
int x=max(0ll,upper_bound(st1+1,st1+top1+1,now)-st1-1);
MOD(dp[pos[c[s2]]]+=(dp1[top1]-dp1[x]+mod)%mod);
s2++;
}
solve(mid+1,r);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
n=rd();
for(int i=1;i<=n;++i)a[i]=rd(),pos[a[i]]=i;
int mx=1e9;
for(int i=1;i<=n;++i){
if(pos[i]<mx)dp[pos[i]]=1;
else dp[pos[i]]=0;
mx=min(mx,pos[i]);
}
solve(1,n);
int ans=0;
mx=0;
for(int i=n;i>=1;--i){
if(pos[i]>mx)MOD(ans+=dp[pos[i]]);
mx=max(mx,pos[i]);
}
printf("%lld\n",ans);
}
return 0;
}