E - Keep Being Substring如果X中有一些位置，它们一直没有被删除，并保留到了Y中，那么这些位置一定形成一个连续段 。有这种位置的情况，操作次数一定比没有的少，因为没有这种位置的情况，X中所有元素都要被删除，Y中所有元素都是手动加上的 。
先看能不能在X中有位置不被删除的情况下完成目标，枚举X中被保留的子段的开头位置i，把X和Y放到一起跑后缀数组+算出LCP数组 。我们的目标是找到j，满足X中以i开头的后缀，与Y中以j开头的后缀的LCP最长 。通过在LCP数组上two-pointers可以轻松找到这样的j 。
然后就是X中全被删光的情况了 。题目要求修改过程中时刻是A的子串，所以我们应该先把X删得只剩下一个字符，然后"跑"到A中某一个Y出现的地方，因为只有一个字符好跑路，多出来的都是累赘，最后肯定都是要删掉的，这些多出来的字符可能导致不是A的子串 。用哈希找出Y在A中出现的所有位置，把这些位置的值\(A_i\)标记为目标值，只要我们达到了其中一个目标值就可以还原出整个Y 。把X中的所有值\(X_i\)标记为起始值，从这些起始值开始跑bfs，两个值之间有边当且仅当它们在A中的某个地方相邻 。这样就通过bfs找到了从"X的一个字符"到"Y的一个字符"的最少操作次数 。
时间复杂度\(O(nlogn)\) 。
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<n;++i)#define repn(i,n) for(int i=1;i<=n;++i)#define LL long long#define ull unsigned long long#define pii pair <int,int>#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){#ifdef LGSfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endif}void termin(){#ifdef LGSstd::cout<<"\n\nPROGRAM TERMINATED";#endifexit(0);}using namespace std;int n;vector <int> s;namespace SA{ int sa[500010],lcp[500010],rk[1000010],cnt[500010],tmp[500010],add,cur; void rsort() {cur=0;for(int i=s.size()-1;i>=s.size()-add;--i) tmp[cur++]=i;rep(i,s.size()) if(sa[i]-add>=0) tmp[cur++]=sa[i]-add;int bd=max(n+3,(int)s.size()+3);rep(i,bd+3) cnt[i]=0;rep(i,s.size()) ++cnt[rk[i]];repn(i,bd+3) cnt[i]+=cnt[i-1];cur=0;for(int i=s.size()-1;i>=0;--i) sa[--cnt[rk[tmp[i]]]]=tmp[i]; } int cmp(int x,int y){return (int)(rk[x]!=rk[y]||rk[x+add]!=rk[y+add]);} void getSA() {rep(i,s.size()+s.size()+3) rk[i]=0;rep(i,s.size()) rk[i]=s[i],sa[i]=i;int m=0;for(int msk=0;m<s.size();++msk){add=(msk==0 ? 0:(1<<(msk-1)));rsort();tmp[sa[0]]=1;repn(i,s.size()-1) tmp[sa[i]]=tmp[sa[i-1]]+cmp(sa[i-1],sa[i]);m=tmp[sa[s.size()-1]];rep(i,s.size()) rk[i]=tmp[i];} } void getLCP() {rep(i,s.size()) --rk[i];lcp[0]=0;rep(i,s.size()){if(rk[i]==0) continue;int lst=(i==0 ? 0:max(0,lcp[rk[i-1]]-1));while(i+lst<s.size()&&sa[rk[i]-1]+lst<s.size()&&s[i+lst]==s[sa[rk[i]-1]+lst]) ++lst;lcp[rk[i]]=lst;} }}int a[200010],xnn,ynn,x[200010],y[200010],ans=1e9,sum[200010],isTarg[200010],dist[200010];ull h[200010],H=11451419,HH,pw[200010];multiset <int> st;vector <int> g[200010];queue <int> q;ull getHash(int lb,int ub){return h[ub+1]-h[lb]*pw[ub-lb+1];}int main(){fileio();cin>>n;rep(i,n) scanf("%d",&a[i]);cin>>xnn;rep(i,xnn) scanf("%d",&x[i]);cin>>ynn;rep(i,ynn) scanf("%d",&y[i]);rep(i,ynn) s.pb(y[i]);s.pb(n+2);rep(i,xnn) s.pb(x[i]);SA::getSA();SA::getLCP();bool hvy=false;int mxc=0;rep(i,s.size()-1){if(SA::sa[i]<ynn)//是y{hvy=true;st.clear();}else{st.insert(SA::lcp[i]);if(hvy) mxc=max(mxc,*st.begin());}}st.clear();hvy=false;for(int i=s.size()-2;i>=0;--i) if(SA::sa[i]!=ynn){if(SA::sa[i]<ynn){hvy=true;st.clear();st.insert(SA::lcp[i]);}else{if(hvy) mxc=max(mxc,*st.begin());st.insert(SA::lcp[i]);}}if(mxc>0) ans=(xnn-mxc)+(ynn-mxc);rep(i,ynn) HH=HH*H+y[i];rep(i,n) h[i+1]=h[i]*H+a[i];pw[0]=1;repn(i,n+3) pw[i]=pw[i-1]*H;rep(i,n-ynn+1){ull hv=getHash(i,i+ynn-1);if(hv==HH) ++sum[i],--sum[i+ynn];}rep(i,n){sum[i+1]+=sum[i];if(sum[i]>0) isTarg[a[i]]=1;}rep(i,n-1) g[a[i]].pb(a[i+1]),g[a[i+1]].pb(a[i]);rep(i,n+3) dist[i]=1e8;rep(i,xnn) if(dist[x[i]]==1e8){dist[x[i]]=0;q.push(x[i]);}while(!q.empty()){int f=q.front();q.pop();rep(i,g[f].size()) if(dist[g[f][i]]==1e8){dist[g[f][i]]=dist[f]+1;q.push(g[f][i]);}}int add=xnn-1+ynn-1;repn(i,n) if(isTarg[i]) ans=min(ans,dist[i]*2+add);cout<<ans<<endl;termin();}
经验总结扩展阅读
- 题解 2021 CCPC 威海站 VP记录
- 支付宝蚂蚁庄园10月23日答题解析
- n维偏序 方法记录
- [题解] Codeforces Dytechlab Cup 2022 1737 A B C D E 题解
- JavaWeb505错误，IDEA版问题解决
- XXI Open Cup, Grand Prix of Belarus 2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest 题解
- P7476 苦涩 题解
- [题解] Codeforces Global Round 22 1738 A B C D E F 题解
- 基础&进阶 线段树学习笔记（一） | P3372 【模板】线段树 1 题解
- 移动端touch拖动事件和click事件冲突问题解决