B
有一个长度为 \(n\) 的排列，你可以进行若干操作，每次操作选择相邻的两个数并删去较大的数。
问最后可以生成多少不同的序列。
设 \(f_i\) 为以 \(i\) 为结尾的序列数。
\(f_i=\sum f_j\) , 仅当区间 \([i,j]\) 内所有数都大于 \(\min(a_i,a_j)\) 时。
边界： \(f_1=1\).
设向前第一个 \(a_k<a_i\) 的下标为 \(k\).
则贡献取之与 \([k,i-1]\) 之间所有数 以及 \([1,k-1]\) 间满足上述条件的数。
我们用递增单调栈维护一下。
那么答案是什么呢，答案是从前往后枚举，当 \(a_i\) 是前缀中最小的数，\(f_i\) 的和。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,mod=1e9+7;
int a[N],n,stk[N],tp,sum[N],val[N],f[N],res;
signed main() {
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
while(a[i]<a[stk[tp]]&&tp) tp--;
f[i]=(sum[i-1]-sum[stk[tp]]+val[tp])%mod;
if(!tp) f[i]++;
stk[++tp]=i;
val[tp]=(val[tp-1]+f[i])%mod;
sum[i]=sum[i-1]+f[i];
}
tp=0;
for(int i=n; i>=1; i--) {
while(a[stk[tp]]>a[i]) --tp;
if(!tp) res=(res+f[i])%mod;
stk[++tp]=i;
}
cout<<(res+mod)%mod;
return 0;
}