[LOJ6198] 谢特
程序员文章站
2022-06-09 14:15:31
之乎者助得甚? 给定字符串$s$和序列$w$,试求 $$ \max_{1\le i using namespace std; const int N=1e5+10; int n,w[N],sa[N],ht[N],rc[N]; char s[N]; void buildSa() { static in ......
之乎者助得甚?
给定字符串\(s\)和序列\(w\),试求
\[
\max_{1\le i<j\le n} lcp(i,j)+(w_i\veebar w_j)
\]
似乎这样的东西都能很好的用sa(height)+启发式合并来完成?
可以联系思考。
#include <bits/stdc++.h> using namespace std; const int n=1e5+10; int n,w[n],sa[n],ht[n],rc[n]; char s[n]; void buildsa() { static int c[n]; int i,p,k,m=128,*x=ht,*y=rc; for(i=0; i<=m; ++i) c[i]=0; for(i=1; i<=n; ++i) c[x[i]=s[i]]++; for(i=1; i<=m; ++i) c[i]+=c[i-1]; for(i=n; i>=1; --i) sa[c[x[i]]--]=i; for(k=1; k<n; k<<=1) { for(i=n-k+1,p=0; i<=n; ++i) y[++p]=i; for(i=1; i<=n; ++i) if(sa[i]>k) y[++p]=sa[i]-k; for(i=1; i<=m; ++i) c[i]=0; for(i=1; i<=n; ++i) c[x[y[i]]]++; for(i=1; i<=m; ++i) c[i]+=c[i-1]; for(i=n; i>=1; --i) sa[c[x[y[i]]]--]=y[i]; swap(x,y), x[sa[1]]=p=1; for(i=2; i<=n; ++i) x[sa[i]]= y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p; if((m=p)>=n) break; } for(i=1; i<=n; ++i) rc[sa[i]]=i; for(i=1,k=0; i<=n; ++i) { p=sa[rc[i]-1]; if(k) k--; while(s[p+k]==s[i+k]) k++; ht[rc[i]]=k; } } int tot,top,stk[n*18]; int ll[n],rr[n],bl[n],siz[n],ch[n*18][2]; pair<int,int> h[n]; int newnode() { return top?stk[top--]:++tot; } void fucknode(int x) { stk[++top]=x; ch[x][0]=ch[x][1]=0; } void insert(int x,int w) { for(int i=16; ~i; --i) { if(!ch[x][(w>>i)&1]) ch[x][(w>>i)&1]=newnode(); x=ch[x][(w>>i)&1]; } } int ans,tmp; void query(int x,int y,int d,int now) { if(d<0) { tmp=max(tmp,now); return; } for(int k=0; k<2; ++k) if(ch[x][k]) { if(ch[y][k^1]) query(ch[x][k],ch[y][k^1],d-1,now|(1<<d)); else query(ch[x][k],ch[y][k],d-1,now); } } void merge(int x,int y,int d) { if(d<0) return; for(int k=0; k<2; ++k) if(ch[x][k]) { if(!ch[y][k]) ch[y][k]=newnode(); merge(ch[x][k],ch[y][k],d-1); fucknode(ch[x][k]); } } int main() { // freopen("c:/users/hsy/downloads/2.in","r",stdin); scanf("%d%s",&n,s+1); for(int i=1; i<=n; ++i) scanf("%d",w+i),newnode(); buildsa(); for(int i=2; i<=n; ++i) h[i-1]=make_pair(-ht[i],i); for(int i=1; i<=n; ++i) { ll[i]=rr[i]=bl[i]=i; siz[i]=1; insert(i,w[sa[i]]); } sort(h+1,h+n); for(int i=1; i<n; ++i) { int len=-h[i].first; int x=bl[h[i].second]; int y=bl[h[i].second-1]; if(siz[x]>siz[y]) swap(x,y); tmp=0; query(x,y,16,0); ans=max(ans,tmp+len); for(int j=ll[x]; j<=rr[x]; ++j) bl[j]=y; ll[y]=min(ll[x],ll[y]); rr[y]=max(rr[x],rr[y]); siz[y]+=siz[x]; merge(x,y,16); } printf("%d\n",ans); return 0; }