利用RMQ求子串lcp的基础题,这个板子是我之前的,比较蠢的一种实现
后面试试用最新的板子AC一下
#include<bits/stdc++.h>
#define ll long long
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
#define per(ii,a,b) for(int ii=b;ii>=a;--ii)
using namespace std;
const int maxn=2e5+10,maxm=2e6+10;
const ll INF=0x3f3f3f3f,mod=1e9+7;
int casn,n,m,k;
const int csize=131;
char s[maxn];
class suffix{public:
int sa[maxn],rank[maxn],h[maxn];
int wa[maxn],wb[maxn],wc[maxn],wd[maxn];
char *str;
void geth(int n){
int i,j,k=0;
for(i=1;i<=n;++i) rank[sa[i]]=i;
for(i=0;i<n;h[rank[i++]]=k)
for(k?k--:0,j=sa[rank[i]-1];str[i+k]==str[j+k];++k);
}
void getsa(char *_s,int n,int m){
str=_s;
int i,j,p,*x=wa,*y=wb,*t;
for(int i=0;i<m;++i) wd[i]=0;
for(int i=0;i<n;++i) wd[x[i]=str[i]]++;
for(int i=1;i<m;++i) wd[i]+=wd[i-1];
for(int i=n-1;i>=0;--i) sa[--wd[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p){
for(p=0,i=n-j;i<n;++i) y[p++]=i;
for(i=0;i<n;++i) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0;i<n;++i) wc[i]=x[y[i]];
for(i=0;i<m;++i) wd[i]=0;
for(i=0;i<n;++i) wd[wc[i]]++;
for(i=1;i<m;++i) wd[i]+=wd[i-1];
for(i=n-1;i>=0;--i) sa[--wd[wc[i]]]=y[i];
for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;++i)
x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
}
geth(n-1);
}
}suf;
class stable{public:
int dp[21][maxn];
void cal(int *a,int n){
rep(i,1,n) dp[0][i]=a[i];
for(int j=1;(1<<j)<=n;j++) for(int i=1;i+(1<<j)-1<=n;++i)
dp[j][i]=min(dp[j-1][i],dp[j-1][i+(1<<(j-1))]);
}
int query(int l,int r){
int lg=0;
while((1<<(lg+1))<=r-l+1) ++lg;
return min(dp[lg][l],dp[lg][r-(1<<lg)+1]);
}
}st;
int main() {
while(cin>>(s)){
n=strlen(s);s[n]='0';
suf.getsa(s,n+1,233);
st.cal(suf.h,n);
cin>>m;
ll ans1=m,ans2=2*m+1;
ll a,b;cin>>a>>b;
ans1+=b-a;ans2+=b-a;
m--;
while(m--){
ll c,d,len;cin>>c>>d;
if(c==a) len=min(d-c,b-a);
else {
int s=suf.rank[a],t=suf.rank[c];
if(s>t) swap(s,t);
len=st.query(s+1,t);
}
len=min(len,min(d-c,b-a));
ans2+=d-c-len;
if(!len) ans2++;
else ans2+=int(log10(len)+1);
ans1+=d-c;
a=c,b=d;
}
cout<<ans1<<' '<<ans2<<endl;
}
return 0;
}