[2022 national game simulation] Bai Loujian - Sam, rollback Mo team, second offline

Non original link

Title Description

Answer key

Encounter this problem of finding the number of substrings , The first time I think of SAM.

Yes $S_2$ Build out SAM after , We can be in its $\mathrm{parent}\mathrm{tree}$ Do some pretreatment on , Record the maximum value of the ancestor node answer of each node . And then in $S_1$ Make scanning lines in the corresponding interval of , Each time we find the longest suffix that can be matched, we can quickly find its contribution to the answer .

From the violent process above , We can quickly expand the range of inquiries 1, And maintain the answer at the same time , But shrinking is not enough . So I'm thinking about online or $Poly(\log n)$ After the solution fails , We can naturally think of using rollback Mo team .

Because both sides need to expand , So we need to build positive and negative strings SAM. Due to rollback, the starting point for Mo team to expand to the right is $\sqrt{n}$ individual , So violence can be pretreated .

Expand to the left , Preprocess to locate $S_1$ The longest string that can be matched at each position on the back is SAM After the node on , Each expansion only requires a doubling jump ancestor to locate the corresponding node of the substring in the interval , then $O(1)$ Just calculate the answer .

So I got a $O(n\sqrt{n}\log n)$ How to do it , My constant is obviously unacceptable .

Consider this $\log n$ Optimized , That is, you don't have to double your search for ancestors , And in a faster way .

One offline has come to an end , We can consider going offline twice . The specific way is , Take the request to find ancestors offline and hang it to SAM On , And then in SAM Do on DFS, Use a data structure to maintain which ancestor each length corresponds to .

Analyze the operands and find , The number of modifications is $O(n)$ Of , The number of queries is $O(n\sqrt{n})$ Of , So use another block $O(\sqrt{n})$ modify ,$O(1)$ Query can be .

The final complexity optimization is $O(n\sqrt{n})$, In advance reserve Skill cards often work better .

Code

#include<bits/stdc++.h>//JZM yyds!!
#define ll long long
#define lll __int128
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define END putchar('\n')
#define lowbit(x) ((x)&-(x))
#define inline jzmyyds
using namespace std;
const int MAXN=1e5+3;
const ll INF=1e17;
ll read(){
    
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){
    if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='\n'){
    
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt>0)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
using pii=pair<int,int>;
char s[MAXN],in[MAXN];
ll qa[33000005],fx[330][MAXN];
int QN,B,BB,n,m,q,pt[MAXN],lt[MAXN],L[MAXN],R[MAXN];
struct itn{
    int ch[26],fa,len;};
int bf[MAXN],bg[330];
void cov(int L,int R,int d){
    
	for(int e=(L-1)/BB,l=e*BB+1;l<=m;l+=BB,e++){
    
		int r=min(m,l+BB-1);
		if(l>R)break;
		if(l>=L&&r<=R)bg[e]=d;
		else for(int i=max(l,L),lm=min(R,r);i<=lm;i++)bf[i]=d;
	}
}
void clr(int L,int R){
    
	for(int e=(L-1)/BB,l=e*BB+1;l<=m;l+=BB,e++){
    
		int r=min(m,l+BB-1);
		if(l>R)break;
		if(l>=L&&r<=R)bg[e]=0;
		else for(int i=max(l,L),lm=min(R,r);i<=lm;i++)bf[i]=0;
	}
}
struct SAM{
    
	itn sam[MAXN<<1];
	int las,tot,t[MAXN<<1],sv[MAXN<<1];
	ll pm[MAXN<<1];
	vector<int>G[MAXN<<1];
	vector<pii>sk[MAXN<<1];
	SAM(){
    las=tot=1;}
	void samadd(int c){
    
		int p=las,np=las=++tot;sam[np].len=sam[p].len+1;
		for(;p&&!sam[p].ch[c];p=sam[p].fa)sam[p].ch[c]=np;
		if(!p)sam[np].fa=1;
		else{
    int q=sam[p].ch[c],nq;
			if(sam[q].len==sam[p].len+1)sam[np].fa=q;
			else{
    
				nq=++tot,sam[nq]=sam[q],sam[nq].len=sam[p].len+1;
				sam[q].fa=sam[np].fa=nq;
				for(;p&&sam[p].ch[c]==q;p=sam[p].fa)sam[p].ch[c]=nq;
			}
		}t[np]++;
	}
	void pdfs(int x){
    
		for(int&v:G[x])pdfs(v),t[x]+=t[v];
	}
	void build(){
    
		for(int i=2;i<=tot;i++)G[sam[i].fa].push_back(i);
		for(int i=1;i<=tot;i++)sk[i].reserve(sv[i]);
		pdfs(1);
	}
	void dfs(int x,ll PM,bool dt){
    
		pm[x]=PM,PM=max(PM,1ll*sam[x].len*t[x]);
		if(x>1&&dt)cov(sam[sam[x].fa].len+1,sam[x].len,x);
		for(auto&it:sk[x]){
    
			if(it.fi>=sam[x].len)qa[it.se]=PM;
			else{
    
				int y=max(bf[it.fi],bg[(it.fi-1)/BB]);
				qa[it.se]=max(1ll*it.fi*t[y],pm[y]);
			}
		}
		for(int&v:G[x])dfs(v,PM,dt);
		if(x>1&&dt)clr(sam[sam[x].fa].len+1,sam[x].len);
	}
}P,Q;
int main()
{
    
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
	*new(int)=scanf("%s%s",s+1,in+1);
	n=strlen(s+1),m=strlen(in+1),B=ceil(sqrt(n)),BB=ceil(sqrt(m));
	for(int i=1;i<=m;i++)P.samadd(in[i]-'a');
	P.build(),P.dfs(1,0,0);
	for(int l=1,e=0;l<=n;l+=B,e++){
    
		int p=1,le=0;
		for(int i=l;i<=n;i++){
    
			int c=s[i]-'a';
			while(p>1&&!P.sam[p].ch[c])p=P.sam[p].fa;
			le=min(le,P.sam[p].len);
			if(P.sam[p].ch[c])p=P.sam[p].ch[c],le++;
			fx[e][i]=max(fx[e][i-1],max(P.pm[p],1ll*le*P.t[p]));
		}
	}
	
	for(int i=m;i>0;i--)Q.samadd(in[i]-'a');
	for(int i=n,le=0,p=1;i>0;i--){
    
		int c=s[i]-'a';
		while(p>1&&!Q.sam[p].ch[c])p=Q.sam[p].fa;
		le=min(le,Q.sam[p].len);
		if(Q.sam[p].ch[c])p=Q.sam[p].ch[c],le++;
		pt[i]=p,lt[i]=le;
	}
	// Because of the special problem , Roll back Mo team without sorting , Directly calculate with the preprocessed value 
	q=read();
	for(int i=1;i<=q;i++){
    
		int l=L[i]=read(),r=R[i]=read(),el=(l-1)/B,er=(r-1)/B;
		if(el==er){
    for(int j=r;j>=l;j--)Q.sv[pt[j]]++;
		}else for(int j=el*B+B;j>=l;j--)Q.sv[pt[j]]++;
	}Q.build(),QN=0;
	for(int i=1;i<=q;i++){
    // Second offline 
		int l=L[i],r=R[i],el=(l-1)/B,er=(r-1)/B;
		if(el==er){
    
			for(int j=r;j>=l;j--)
				Q.sk[pt[j]].emplace_back(min(r-j+1,lt[j]),++QN);
		}else{
    
			for(int j=el*B+B;j>=l;j--)
				Q.sk[pt[j]].emplace_back(min(r-j+1,lt[j]),++QN);
		}
	}Q.dfs(1,0,1),QN=0;
	for(int i=1;i<=q;i++){
    
		int l=L[i],r=R[i],el=(l-1)/B,er=(r-1)/B;
		ll ans=0;
		if(el==er){
    
			for(int j=r;j>=l;j--)ans=max(ans,qa[++QN]);
		}else{
    
			ans=fx[el+1][r];
			for(int j=el*B+B;j>=l;j--)ans=max(ans,qa[++QN]);
		}
		print(ans);
	}
	return 0;
}