HNOI2019 JOJO

JOJO"/>

HNOI2019 JOJO

HNOI2019 JOJO

jojo这个坑填上了，然鹅还有序列这个题啊啊啊啊啊啊

膜

可持久化这个东西没有强制在线就是假的，直接建树dfs就行了

这题是kmp的加强版，每次会加一堆相同的数进来

先想一个50分的傻逼暴力，因为这题和kmp一样当然往kmp方向想，设\(nxt_i\)表示第\(i\)段字符的最后一个字符的\(nxt\)。

那么有一个优化，看一下求\(nxt\)的过程，如果新加了一段\(y\)个\(x\)字符，上一个\(nxt_i\)必须满足\(A[nxt_i+1]=x\)才行，否则会跳\(nxt\)，题目还给了相邻两段字符不同，那么\(A[nxt_i+1]=x\)也意味着\(A[nxt_i+1]\neq A[nxt_i]\)，也即\(nxt_i\)是一段的最后一个字符，如果不是可以继续跳知道是为止

那么\(nxt\)只需要记所在的段了

再来看怎么求\(\sum\)真正的\(nxt\)。可以从假的\(nxt\)数组一直跳，并且一边跳一边皮配一段后缀。具体看代码，懒得写了。

这样复杂度是\(O(n^2)\)假的，但原题可以AC（然后被神仙卡掉）

考虑怎么把复杂度优化成真的，跳\(nxt\)时，如果字符串存在周期，那么直接跳到第一个周期。

#include<bits/stdc++.h>
#define il inline
#define rg register
#define vd void
#define mod 998244353
#define ll long long
il int gi(){int x=0,f=0;char ch=getchar();while(!isdigit(ch))f^=ch=='-',ch=getchar();while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return f?-x:x;
}
int qop[100010],qx[100010];
std::vector<int>s[100010];
char qch[100010];
int ans[100010];
char nowch[100010];
int len,nowlen[100010],nowslen[100010],nxt[100010];
int res[100010];
il int getsum(int l,int r){return 1ll*(l+r)*(r-l+1)/2%mod;}
il vd dfs(int x){if(qch[x])do{++len;nowch[len]=qch[x];nowlen[len]=qx[x];nowslen[len]=nowslen[len-1]+qx[x];nxt[len]=0;res[len]=0;if(len==1){res[len]=getsum(1,nowlen[len]-1);break;}int p=nxt[len-1],lastgap=len-nxt[len-1];while(p&&(nowch[p+1]!=nowch[len]||nowlen[p+1]!=nowlen[len])){if(p-nxt[p]==lastgap)p=p%lastgap+lastgap;lastgap=p-nxt[p],p=nxt[p];}if(p||(nowch[1]==nowch[len]&&nowlen[1]<=nowlen[len]))++p;nxt[len]=p;p=nxt[len-1];lastgap=len-1-p;int matchedlen=0;while(matchedlen<nowlen[1]&&p){if(nowch[p+1]==nowch[len]&&nowlen[p+1]>matchedlen){res[len]=(res[len]+getsum(nowslen[p]+matchedlen+1,nowslen[p]+std::min(nowlen[p+1],nowlen[len])))%mod;matchedlen=std::min(nowlen[len],nowlen[p+1]);}if(p-nxt[p]==lastgap)p=p%lastgap+lastgap;lastgap=p-nxt[p],p=nxt[p];}if(matchedlen<nowlen[len]&&nowch[1]==nowch[len]){res[len]=(res[len]+getsum(matchedlen+1,std::min(nowlen[1],nowlen[len])))%mod;matchedlen=std::min(nowlen[len],nowlen[1]);res[len]=(res[len]+1ll*nowlen[1]*(nowlen[len]-matchedlen))%mod;}res[len]=(res[len]+res[len-1])%mod;}while(0);ans[x]=res[len];for(auto i:s[x])dfs(i);if(qch[x])--len;
}
int main(){
//  freopen("jojo.in","r",stdin);
//  freopen("jojo.out","w",stdout);int n=gi();for(int i=1;i<=n;++i){qop[i]=gi(),qx[i]=gi();if(qop[i]==1)qch[i]=getchar();else qch[i]=0;if(qop[i]==1)s[i-1].push_back(i);else s[qx[i]].push_back(i);}dfs(0);for(int i=1;i<=n;++i)printf("%d\n",ans[i]);return 0;
}

转载于:.html