[牛客2020第4场]牛半仙的妹子序列

本文主要是介绍[牛客2020第4场]牛半仙的妹子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛半仙的妹子序列

题解

《关于我因过于这道题卡常而将其称为"贞卡常"的这件事》

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

这道题应该很容易看出是一个dp，40pts的$O(n^2)$的dp式子应该是很好想的。
我们定义$d{p}_i$为在只关注第$i$个数到第$n$个数之间的序列构成合法序列的方案数。
容易得到方程式

$d{p}_i={\sum }_{j=i+1}^n[满足条件]d{p}_j$。

而答案就是我们的$d{p}_0$。

这种方式的dp是明显可以进行优化的，我们先考虑$d{p}_i$对那些值产生了贡献。
容易发现，$d{p}_i$产生贡献的$d{p}_j$满足条件
[ j < i ∧ v j < v i ∧ m a x k = j + 1 i { d p k < d p j } ] [j<i \wedge v_{j}<v_{i} \wedge max_{k=j+1}^{i}\{dp_{k}<dp_{j}\}] [j<i∧vj​<vi​∧maxk=j+1i​{dpk​<dpj​}]。
而这个条件我们需要想办法对其进行维护。
对于这个我们可以先按权值建一棵FHQ_Treap，每次进行操作时将值在$[v_i,n+1)$中的树给裂出去，在那棵值域小于$v_i$的数加上$d{p}_i$。

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

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

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

源码

#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;
}

$谢谢$

这篇关于[牛客2020第4场]牛半仙的妹子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---