牛半仙的妹子序列

题解：

考虑 $DP$ 。

$f_{i}=\sum_{j<i,a_{j}<a_{i},\nexists k, j<k<i , a_{j}<a_{k}<a_{i}} f_{j}$

对于第 $i$ 个点，考虑哪些点对 $i$ 是有贡献的。记点 $x$ 到点 $i$ 间比 $a_{x}$ 大的最小值为 $mi_x$ ，那么只要 $mi_x>a_i$ 那么这个点就会有贡献。所以我们要维护这个 $mi_x$ 。

怎么维护呢，对于一个新加入的值 $v$ ，那些值小于 $v$ 的点的 $mi$ 就要和 $v$ 取 $min$ 。

用 $set$ 维护这个 $mi[]$ ，只观察 $mi[]$ ，发现每次操作可以看成比 $v$ 大的数变成 $v$ ，每次操作都会少一段值相同的区间。总共只有 $n$ 段区间，所以最多操作 $n$ 次，时间复杂度: $O(n log n)$

用线段树处理应该复杂度一样的吧（作者太菜不会证）。

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int mod=998244353;
const int N=1e6+5;
int n,m,ans,a[N],f[N];
struct node{
    int val,gs;
}tree[N*4];
node operator + (node a,node b)
{
    if(a.val>b.val)return a;
    if(a.val<b.val)return b;
    return (node){a.val,(a.gs+b.gs)%mod};
}
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
void change(int nod,int l,int r,int L,int R,int x)
{
    if(l>=L&&r<=R&&tree[nod].val<x)return;
    if(l>R||r<L)return;
    if(l==r)
    {
        tree[nod].val=x;
        return;
    }
    int mid=(l+r)/2;
    change(nod*2,l,mid,L,R,x);
    change(nod*2+1,mid+1,r,L,R,x);
    tree[nod]=tree[nod*2]+tree[nod*2+1];
}
node find(int nod,int l,int r,int L,int R)
{
    if(l==L&&r==R)return tree[nod];
    int mid=(l+r)/2;
    if(R<=mid)return find(nod*2,l,mid,L,R);
    else if(L>mid)return find(nod*2+1,mid+1,r,L,R);
    else return find(nod*2,l,mid,L,mid)+find(nod*2+1,mid+1,r,mid+1,R);
}
void change2(int nod,int l,int r,int x,int val)
{
    if(l==r)
    {
        tree[nod].val=n+1;
        tree[nod].gs=val;
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid)change2(nod*2,l,mid,x,val);
    else change2(nod*2+1,mid+1,r,x,val);
    tree[nod]=tree[nod*2]+tree[nod*2+1];
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)
    {
        change(1,1,n,1,a[i],a[i]);
        node x=find(1,1,n,1,a[i]);
        if(x.val==a[i])f[i]=x.gs;
        else f[i]=1;
        change2(1,1,n,a[i],f[i]);
    }
    cout<<tree[1].gs;
    return 0;
}