[BZOJ3499] PA2009 Quasi-template

被这题毒死了…… 调了这题一万年最后是线段树合并写挂了，身败名裂…… _____________ 给定一个字符串，定义一个子串是合法的当且仅当这个子串可以覆盖这整个串，允许重复覆盖也允许在头部和尾部进行不完全的覆盖 求有多少个本质不同的合法子串，并且输出长度最小的合法子串，如果有多个合法的串输出字典序最小的那个 ____________ ## 本题题解 让我们先来忽略那个要命的最小字典序串，来考虑怎么数所有本质不同的合法子串数目 那么既然是本质不同的合法子串我们就会想到利用后缀自动机的性质来去重 为了方便接下来的讨论我们把这个字符串**反过来**跑后缀自动机，这样的话我们的parent树就和后缀树非常像 那么我们可以枚举后缀自动机上的每一个节点，显然这个节点会对应很多的子串，不过这些子串的right集合全部相同，那么我们需要求出有几个长度l使得这个节点对应的子串是合法的 然后我们画一下图会发现这个串大概会长这样  那么如果我们不考虑字符串的头部和尾部可以被不完全的覆盖这个情况的话，我们可以给这个字符串的长度l定一个初步的取值范围,假设right集合之间相邻两项差的最大值为mx的话，我们的l的取值范围应该是介于$(max(fa.len+1,mx),len)$ 之间的，$fa.len+1,len$是由后缀自动机的定义得到的，而这个端点的长度至少要比相邻两项长度差的最大值大否则在中间的部分就会有空隙然后我们的字符串就不合法了…… 怎么求出这个mx值呢？我们可以在线段树上每个节点维护一下区间中pos的min值和区间中pos的max值以及区间中的mx值，然后合并两个孩子节点的柿子自己手玩一下画画图或者直接看我代码就行了,这样我们就可以使用线段树合并来维护right集合了 现在我们来考虑一些比较要命的问题，我们字符串的头部和尾部可以被不完全的覆盖，我们对于这一部分需要特殊处理 我们先来考虑头部的情况，此时这个串的头部大概是这种情况  我们设$P$为这个子串第一次出现的位置，$i$是这个子串第一次出现位置的右端点 那么我们可以肥肠直观的看到图中的红色部分是相等的，那么换句话说红色部分应该是i这个前缀的一个公共前后缀，那么如果i这个前缀的最长公共前后缀的长度大于等于$P-1$的话，感性理解一下我们会发现i这个位置就会变成一个合法的位置(具体证明不太好证加之这东西还是不怎么反直觉就请读者自行理会了~) 接下来假设我们求出了字符串长度的取值范围是在$(l,r)$的取值范围之间的话我们就会发现我们现在就是想求$(p+l-1,p+r-1)$这个区间里有几个数字的$nxt$值大于等于$p-1$，这显然是个二维数点问题，我们可以使用主席树来轻松的搞定他~ 接下来问题就是我们怎么求出l的取值范围了 我们发现l的取值范围并不是肥肠的好搞。。。,您可能会想，我们是不是把l接着和(n+1-right集合中的最大值)取个max这题就做完了？ 那么请把后缀自动机中right集合的定义念一遍，这个子串在字符串中出现位置右端点的集合，请注意这里的出现是指和母串完全匹配而不是指别的东西 因此当我们的len+right集合中的最大值大于n之后我们的最大值就会直接从right集合中消失掉……，这样的话我们的right集合中最大值就不是我们想的意义了，因此不能直接用(n+1-right集合中的最大值)来更新l 那么我们发现肯定会有这个子串的一个前缀出现在字符串的最后方，接下来我们需要做的就是尽可能延长这个子串的前缀，因为这个前缀长度越长我们的限制就越小 发现一个很棒的事实是这个前缀所对应的sam节点一定出现在我们这个点到parent树的链上了，因此我们先dfs一遍预处理出每个节点中right集合的最小值，最大值，区间中的最大差值，然后再次dfs一遍处理出每个节点的最长匹配前缀所在的位置，然后就可以用来更新答案了 具体点来讲，我们设这个最长前缀的出现位置是f,如果这个点的max值(right集合中的max值)+len-1=n的话我们就将f值更新到这个节点的mx，然后求l的取值范围的时候左端点额外的和f-max取一下max就可以求出正确的l了 好了到此位置我们凭借后缀自动机上一些精妙的贪心操作以及使用了最长公共前后缀的性质处理出了有几个本质不同的合法子串了 现在我们再码上两个k来解决输出字典序最小值的问题 怎么处理这个问题呢？ 刚才我们对于后缀自动机上每一个节点处理出了一个区间$(p+l-1,p+r-1)$, 假如在这个区间有合法子串的话我们其实就是在这个区间当中找到一个最小的i使得$p-1 \leq nxt(i)$接下来我们只需要把这个询问离线，然后把所有点按照nxt丢到set里面去lower_bound就可以做到查询出最小长度的解了 蛤？字典序最小的限制？ 会比较两个字符串字典序大小吗？二分哈希求出lcp然后直接比较就行了 然后这道大duliu题就写完了~ 上代码~ ```C #include<cstdio> #include<algorithm> #include<set> #include<vector> using namespace std;const int N=2*1e5+10;typedef unsigned long long ll; int n;int len[N<<1];int v[N<<1];int x[N<<1];int ct;int al[N<<1]; char mde[N];int nxt[N];ll ans;ll hsh[N];ll mi[N];int st[N<<1];int ed[N<<1];int del[N<<1]; ll NANS;char mdeA[N]; inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;} inline bool cmp(const int& l1,const int& r1,const int& l2,const int& r2) {return (mi[n-l1+1]*(hsh[r1]-hsh[l1-1]))==(mi[n-l2+1]*(hsh[r2]-hsh[l2-1]));} struct str { int l;int r; friend bool operator <(str a,str b) { if(a.r-a.l==b.r-b.l) { int l=0;int r=a.r-a.l+1; while(l!=r){int mid=(l+r+1)>>1;if(cmp(a.l,a.l+mid-1,b.l,b.l+mid-1))l=mid;else r=mid-1;} if(l==a.r-a.l+1)return false;else return mde[a.l+l]<mde[b.l+l]; }else return (a.r-a.l)<(b.r-b.l); } }res; struct linetree { int mi[20*N];int mx[20*N];int ans[20*N];int s[20*N][2];int ct; linetree(){mi[0]=0x3f3f3f3f;mx[0]=-1;ans[0]=0;} inline void ins(int p,int l,int r,int pos) { mi[p]=mx[p]=pos;ans[p]=0;if(r-l==1){return;}int mid=(l+r)/2; if(pos<=mid)ins(s[p][0]=++ct,l,mid,pos);else ins(s[p][1]=++ct,mid,r,pos); } inline void mg(int p1,int p2) { if(s[p1][0]&&s[p2][0])mg(s[p1][0],s[p2][0]);else if(s[p2][0])s[p1][0]=s[p2][0]; if(s[p1][1]&&s[p2][1])mg(s[p1][1],s[p2][1]);else if(s[p2][1])s[p1][1]=s[p2][1]; int ls=s[p1][0];int rs=s[p1][1]; if(ls&&rs) { ans[p1]=max(mi[rs]-mx[ls],max(ans[ls],ans[rs])); mi[p1]=min(mi[ls],mi[rs]);mx[p1]=max(mx[ls],mx[rs]); } else if(ls){ans[p1]=ans[ls];mi[p1]=mi[ls];mx[p1]=mx[ls];} else if(rs){ans[p1]=ans[rs];mi[p1]=mi[rs];mx[p1]=mx[rs];} } }lt; struct sam { int mp[N<<1][30];int fa[N<<1];int ct;inline void ih(){ct=n+1;} inline void ins(int nw,int ed,int c) { len[nw]=len[ed]+1;int p;for(p=ed;p&&mp[p][c]==0;p=fa[p])mp[p][c]=nw; if(p==0){fa[nw]=n+1;return;}int q=mp[p][c]; if(len[q]==len[p]+1){fa[nw]=q;return;}len[++ct]=len[p]+1; for(int i=1;i<=26;i++)mp[ct][i]=mp[q][i]; for(;p&&mp[p][c]==q;p=fa[p])mp[p][c]=ct; fa[ct]=fa[q];fa[q]=fa[nw]=ct; } inline void build() { for(int i=1;i<=ct;i++)if(fa[i])add(fa[i],i);lt.ct=n; for(int i=1;i<=n;i++)lt.ins(i,0,n,i); } }sam; namespace plt1 { int v[20*N];int s[20*N][2];int ct; inline void ins(int p1,int p2,int l,int r,int pos) { v[p1]=v[p2]+1;if(r-l==1){return;}int mid=(l+r)/2; if(pos<=mid)s[p1][1]=s[p2][1],ins(s[p1][0]=++ct,s[p2][0],l,mid,pos); else s[p1][0]=s[p2][0],ins(s[p1][1]=++ct,s[p2][1],mid,r,pos); } inline int qry(int p,int l,int r,int dl,int dr) { if(p==0||(l==dl&&r==dr)){return v[p];}int mid=(l+r)/2;int res=0; if(dl<mid)res+=qry(s[p][0],l,mid,dl,min(dr,mid)); if(mid<dr)res+=qry(s[p][1],mid,r,max(dl,mid),dr);return res; } } namespace plt2 { struct qry{int l;int r;}; set <int> s;vector <qry> ve[N];vector <int> pos[N]; inline void pb(int l,int r,int p){ve[p].push_back((qry){l,r});} inline void solve() { for(int i=1;i<=n;i++)pos[nxt[i]].push_back(i); for(int i=n;i>=0;i--) { for(vector <int>:: iterator it=pos[i].begin();it!=pos[i].end();++it) s.insert(*it); for(vector <qry>:: iterator it=ve[i].begin();it!=ve[i].end();++it) res=min(res,(str){it->l,*s.lower_bound(it->r)}); } } } inline int dfs(int u) { int ret=(u<=n)?u:-1; for(int i=al[u];i;i=x[i]) {int vp=dfs(v[i]);if(ret==-1)ret=vp;else if(vp!=-1)lt.mg(ret,vp);} st[u]=lt.mi[ret];ed[u]=lt.mx[ret];del[u]=lt.ans[ret];return ret; } inline void dfs2(int u,int f) { int r=st[u]+len[u]-1;int l=st[u]+max(max(del[u],f-ed[u]),len[sam.fa[u]]+1)-1; if(l<=r) { int ret=plt1::qry(r,-1,n-1,st[u]-2,n-1)-plt1::qry(l-1,-1,n-1,st[u]-2,n-1); if(ret!=0){ans+=ret,plt2::pb(st[u],l,st[u]-1);} }if(ed[u]+len[u]-1==n)f=ed[u]; for(int i=al[u];i;i=x[i])dfs2(v[i],f); } int main() { scanf("%s",mde+1);for(n=1;mde[n+1]!='\0';n++);sam.ih(); for(int i=n;i>=1;i--)sam.ins(i,i+1,mde[i]-'a'+1);sam.build(); mi[0]=1;for(int i=1;i<=n;i++)mi[i]=mi[i-1]*29; for(int i=1;i<=n;i++)hsh[i]=hsh[i-1]+mi[i-1]*(mde[i]-'a'+1); for(int i=2;i<=n;i++) { for(nxt[i]=nxt[i-1];nxt[i]&&mde[nxt[i]+1]!=mde[i];nxt[i]=nxt[nxt[i]]); nxt[i]+=(mde[i]==mde[nxt[i]+1]); }plt1::ct=n;res=(str){1,n}; for(int i=1;i<=n;i++)plt1::ins(i,i-1,-1,n-1,nxt[i]); dfs(n+1);dfs2(n+1,n+1);plt2::solve();printf("%lld\n",ans); for(int i=res.l;i<=res.r;i++)printf("%c",mde[i]);printf("\n");return 0; } ```