T4牛半仙的妹子序列

原博客食用效果更佳

题解

场上被卡常了，下来加了几个优化就卡过去了。

这道题应该很容易看出是一个dp，40pts的的dp式子应该是很好想的。
我们定义为在只关注第个数到第个数之间的序列构成合法序列的方案数。
容易得到方程式

。

而答案就是我们的。

这种方式的dp是明显可以进行优化的，我们先考虑对那些值产生了贡献。
容易发现，产生贡献的满足条件。
而这个条件我们需要想办法对其进行维护。
对于这个我们可以先按权值建一棵FHQ_Treap，每次进行操作时将值在中的树给裂出去，在那棵值域小于的数加上。

但我们如何保证后半段条件呢？

我们可以对Treap上的每个点加上一个的值，表示号节点的坐标。而每次操作后都将操作的那个对应的点从树中删掉。保证剩下的点都的值都小于删掉的点。加的过程中当且仅当所有的在点右边的点(即在原序列中值比它大的点)的值都小于它时才对其进行加dp值得操作。
由于这个值得加操作比较复杂，可能会被卡到，总时间复杂度存在着被卡掉的风险，所以我们需要对其加几个优化。

我们用一个二元组表示。
其中表示当前懒标记加值得大小，而表示需要点的值大于多少时才能加上当前的值。
我们知道，当前点如果可以加上的话，必定满足大于其右边子树的最大值和
如果当前子树的整体都小于的话就回退。
如果当前等于新加的的值的话就不用下传。
其实这两个剪枝再实际操作中都很有作用，可以证明我们最后的时间复杂度是可以过这道题的。
还有一些细枝末节的卡常技巧这里不做阐释。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define MAXN 200005
typedef long long LL;
const int mo=998244353;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
    _T f=1;x=0;char s=getchar();
    while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
    while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
    x*=f;
}
int n,a[MAXN],ad[MAXN];
int add(const int x,const int y){return x+y<mo?x+y:x+y-mo;}
int Max(const int x,const int y){return x>y?x:y;}
class FHQ_Treap{
    private:
        int ch[MAXN][2],rnd[MAXN],val[MAXN];
        int sum[MAXN],maxx[MAXN];pii lzy[MAXN];
        int siz[MAXN],tot,root;
        int newnode(const int v){int x=++tot;siz[x]=1;rnd[x]=rand();maxx[x]=val[x]=v;return x;}
        inline void updata(const int x){
            siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;maxx[x]=val[x];
            if(ch[x][0])maxx[x]=Max(maxx[x],maxx[ch[x][0]]);
            if(ch[x][1])maxx[x]=Max(maxx[x],maxx[ch[x][1]]);
        }
        void downdata(const int x){
            if(!lzy[x].first)return ;
            if(maxx[x]<lzy[x].second){lzy[x]=make_pair(0,0);return ;}
            const int tm2=Max(maxx[ch[x][1]],lzy[x].second-1);
            if(tm2<val[x])sum[x]=add(sum[x],lzy[x].first);
            if(ch[x][1]){
                if(lzy[ch[x][1]].second==lzy[x].second)lzy[ch[x][1]].first=add(lzy[ch[x][1]].first,lzy[x].first);
                else downdata(ch[x][1]),lzy[ch[x][1]]=lzy[x];
            }
            const int tm1=Max(val[x],maxx[ch[x][1]]);
            if(ch[x][0]&&maxx[ch[x][0]]>tm1){
                const int tmp=Max(lzy[x].second,tm1);
                if(lzy[ch[x][0]].second==tmp)lzy[ch[x][0]].first=add(lzy[ch[x][0]].first,lzy[x].first);
                else downdata(ch[x][0]),lzy[ch[x][0]]=make_pair(lzy[x].first,tmp);
            }
            lzy[x]=make_pair(0,0);
        }
        int merge(const int a,const int b){
            if(!a||!b)return a+b;
            downdata(a);downdata(b);
            if(rnd[a]<rnd[b]){
                ch[a][1]=merge(ch[a][1],b);
                updata(a);return a;
            }
            ch[b][0]=merge(a,ch[b][0]);
            updata(b);return b;
        }
        void split(const int now,const int k,int &x,int &y){
            if(!now){x=y=0;return ;}downdata(now);
            if(k<a[val[now]])y=now,split(ch[now][0],k,x,ch[now][0]);
            else if(k==a[val[now]])x=now,y=ch[now][1],ch[now][1]=0;
            else x=now,split(ch[now][1],k,ch[now][1],y);
            updata(now);
        }
        void build(int &rt,const int l,const int r){
            if(l>r)return ;
            int mid=l+r>>1;rt=newnode(ad[mid]);
            build(ch[rt][0],l,mid-1);
            build(ch[rt][1],mid+1,r);
            updata(rt);
        }
    public:
        void Build(){maxx[0]=-1;build(root,0,n);lzy[root]=make_pair(1,0);}
        inline void query(const int v){
            int x1,y1,x2,y2;split(root,v-1,x1,y1);
            split(y1,v,x2,y2);downdata(x1);downdata(x2);
            lzy[x1]=make_pair(sum[x2],0);root=merge(x1,y2);
        }
        int ask(){downdata(root);return sum[root];}
}Tree;
signed main(){
    srand(191919);
    read(n);for(int i=1;i<=n;++i)read(a[i]),ad[a[i]]=i;
    Tree.Build();for(int i=n;i;--i)Tree.query(a[i]);
    printf("%d\n",Tree.ask());
    return 0;
}