解析

很好的一道SA的題。（覺(jué)得完全可以評(píng)黑了啊qwq）
我一開(kāi)始拿SAM和線段樹(shù)硬做，不斷修正最后發(fā)現(xiàn)自己無(wú)法在可接受復(fù)雜度內(nèi)解決的問(wèn)題，直接GG…
垃圾數(shù)據(jù)還騙到了50分
所以寫(xiě)一道題之前還是要先想仔細(xì)了，確定整個(gè)流程沒(méi)有鍋再寫(xiě)吧，盡量避免寫(xiě)一半發(fā)現(xiàn)不對(duì)再修正甚至直接假掉的情況，還能使實(shí)現(xiàn)時(shí)更加系統(tǒng)簡(jiǎn)潔。

考慮SA。
為什么搜SAM的tag結(jié)果全是拿SA做的啊。

答案顯然具有單調(diào)性，考慮check二分的答案 $L$ 是否合法。
合法的情況可以等價(jià)抽象為：區(qū)間內(nèi)存在兩個(gè)后綴 $p,q$，使得 $lcp(p,q)\le L$ 。
用類似品酒大會(huì)的思路（這個(gè)思路似乎非常常見(jiàn)好用），把所有 $h_i\ge L$ 的 $i,i?1$ 合并，最后就是看區(qū)間內(nèi)是否有兩個(gè)點(diǎn)在同一個(gè)集合內(nèi)。

在線段樹(shù)上存儲(chǔ)每個(gè)結(jié)點(diǎn)左側(cè)在同一集合內(nèi)的結(jié)點(diǎn)最靠右的位置，問(wèn)題轉(zhuǎn)化為查詢 $[l,r?L+1]$ 的最大值是否大于 $L$。
這個(gè)線段樹(shù)可以用主席樹(shù)維護(hù)，每個(gè)并查集集合維護(hù)一個(gè) set，啟發(fā)式合并暴力查找前驅(qū)后綴即可。

時(shí)空復(fù)雜度 $O(nlo{g}^{2}n)$。

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } const int N=1e5+100; const int M=1e6+100; const int mod=1e9;int n,m; char s[N];int sa[N],rk[N],id[N],oldrk[N],cnt[N]; int h[N]; void SA(){int m=300;//printf("%s\n",s+1);for(int i=1;i<=n;i++) ++cnt[rk[i]=s[i]];for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];for(int i=n;i>=1;i--) sa[cnt[rk[i]]--]=i;for(int w=1;m!=n;w<<=1){int p=0;for(int i=n;i>n-w;i--) id[++p]=i;for(int i=1;i<=n;i++){if(sa[i]>w) id[++p]=sa[i]-w;}memset(cnt,0,sizeof(cnt));memcpy(oldrk,rk,sizeof(rk));for(int i=1;i<=n;i++) ++cnt[rk[id[i]]];for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];for(int i=n;i>=1;i--) sa[cnt[rk[id[i]]]--]=id[i];m=0;for(int i=1;i<=n;i++){if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w]) rk[sa[i]]=m;else rk[sa[i]]=++m;}}for(int i=1,y=0;i<=n;i++){if(y) --y;while(s[i+y]==s[sa[rk[i]-1]+y]) ++y;h[rk[i]]=y;}//for(int i=1;i<=n;i++) printf("i=%d %s sa=%d h=%d\n",i,s+sa[i],sa[i],h[i]);return; }struct tree{int ls,rs,mx; }; const int C=100; struct Sefment_Tree{tree tr[N*C];int tot;#define mid ((l+r)>>1)inline int copy(int x){tr[++tot]=tr[x];assert(tot<N*C);return tot;}inline void pushup(int k){tr[k].mx=max(tr[tr[k].ls].mx,tr[tr[k].rs].mx);return;}int ask(int k,int l,int r,int x,int y){if(!k) return 0;if(x<=l&&r<=y) return tr[k].mx;int res=0;if(x<=mid) res=max(res,ask(tr[k].ls,l,mid,x,y));if(y>mid) res=max(res,ask(tr[k].rs,mid+1,r,x,y));return res;}void change(int &k,int l,int r,int p,int w){k=copy(k);if(l==r){tr[k].mx=max(tr[k].mx,w);return;}if(p<=mid) change(tr[k].ls,l,mid,p,w);else change(tr[k].rs,mid+1,r,p,w);pushup(k);}#undef mid }t; int rt[N];set<int>S[N]; set<int>::iterator it; inline int Suf(int k,int w){it=S[k].lower_bound(w);return (it==S[k].end())?0:(*it); } inline int Pre(int k,int w){it=S[k].lower_bound(w);if(it==S[k].begin()) return 0;else{it--;return (*it);} } int fa[N]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]); } void merge(int x,int y,int L){//printf("merge: %d %d L=%d\n",x,y,L); x=find(x);y=find(y);if(S[x].size()>S[y].size()) swap(x,y);//printf(" x=%d y=%d\n",x,y);for(int now:S[x]){int pre=Pre(y,now),suf=Suf(y,now);if(pre) t.change(rt[L],1,n,now,pre);if(suf) t.change(rt[L],1,n,suf,now);//printf(" ins:now=%d pre=%d suf=%d\n",now,pre,suf);}for(int now:S[x]){S[y].insert(now);}S[x].clear();fa[x]=y;return; }struct node{int h,id;bool operator < (const node o)const{return h>o.h;} }p[N];signed main(){#ifndef ONLINE_JUDGE//freopen("a.in","w",stdin);//freopen("a.out","w",stdin);#endifn=read();m=read();//printf("%d\n",n);scanf(" %s",s+1);SA();int num(0);for(int i=1;i<=n;i++){fa[i]=i;S[i].insert(i);if(i>1) p[++num]=(node){h[i],i};}sort(p+1,p+1+num);int pl=1;for(int i=n;i>=0;i--){rt[i]=rt[i+1];while(pl<=num&&p[pl].h==i){if(p[pl].id>1){int x=sa[p[pl].id],y=sa[p[pl].id-1];merge(x,y,i);}++pl;}}for(int i=1;i<=m;i++){int l=read(),r=read(),st=0,ed=n;while(st<ed){int mid=(st+ed+1)>>1;if(t.ask(rt[mid],1,n,l,r-mid+1)>=l) st=mid;else ed=mid-1;}printf("%d\n",st);}return 0; } /* 8 1 aabaabba 4 5*/

總結(jié)

以上是生活随笔為你收集整理的洛谷P7361：拜神（SA、二分、主席树、启发式合并）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。