Description
Solution
不妨先考虑subtask 2
即给出一个字符串S，动态询问[l,r]内本质不同的子串数。
有一个非常套路的做法（来自laofu的2018集训队论文）：
考虑离线。先将这个字符串S的SAM建出来
对于SAM上的一个节点，贡献就是它在[l…r]出现的最后一次被l所截的长度。
我们将所有询问按右端点排序，从左到右扫r。
那么每次相当于在parent树上将一个点到根的路径上的影响全部修改，将这条路径的时间改为相同，并且要撤销之前不同时间标记的影响。
如果把相同时间标记看做一条父亲后代链，那么这个操作就非常像LCT的access操作。
那么我们可以用一个LCT来维护，每次更新相当于access一次，然后对于每一条偏爱链都在线段树上区间+1/-1。
这样由于access均摊是有log条偏爱链，每条都要线段树修改，复杂度就是 O ( n log 2 n ) O(n\log^2 n) O(nlog2n)的。
回到原题。
手玩一波可以感受出来，我们假设将询问的L，R都缩到最近（就是将中间的整串都删去），再一个一个添加整串，从添加的第二个整串开始，以后每新增一个整串，对于答案的增量是相同的，那么我们只需要暴力计算5n以内的就可以了。
可能会被卡常
然而我们有一个更加优美的性质，只需要计算3n以内。
首先假如原串是一个循环串，那么将它缩到它的最小循环节。此时新的串长记为n’
从[l,l+2n’]开始，右端点每右移一位，本质不同的子串数量增加n’。
也就是增加了子串右端为区间右端，子串左端在[l,l+n’-1]这些子串，显然左端>l+n’-1的之前一定计算过，现在只需要确定这些子串之前均未计算过。
假设子串[x,y]之前在[u,v]出现过了，那么显然原串有x-u这个周期
又由于子串[x,y]和[u,v]都包含了一个原串，那么原串又有n-(y-v)=n-(x-u)这个周期。
画一个图可以推出，原串必定还有gcd(n,x-u)这个周期，也就意味着原串还有gcd(n,x-u)长度的循环节
这就与原来的题设矛盾了
因此这样只需要暴力计算3n’以内，可以通过这道题。
Code
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define N 100005
#define M 400005
#define L 800005
#define LL long long
using namespace std;
char ch[N],st[M],ch1[N];
int n,q,q1,t[2*M][2],m,n1,t1[2*M][26],n2,qs[N][3],ti[2*M],mx[2*M],fail[2*M],pt[L],opx,opy;
LL sm[2*M],lz[2*M],s1[M][4];
struct node
{
int x,y,w,p;
friend bool operator <(node x,node y)
{
return x.y<y.y;
}
}ask[M];
void build(int k,int l,int r)
{
if(l==r) {sm[k]=0;return;}
int mid=(l+r)>>1;
t[k][0]=++n1,build(t[k][0],l,mid);
t[k][1]=++n1,build(t[k][1],mid+1,r);
}
void down(int k,int l,int mid,int r)
{
sm[t[k][0]]+=(LL)(mid-l+1)*lz[k];
sm[t[k][1]]+=(LL)(r-mid)*lz[k];
lz[t[k][0]]+=lz[k],lz[t[k][1]]+=lz[k];
lz[k]=0;
}
LL query(int k,int l,int r)
{
if(opx>opy||opy<l||opx>r) return 0;
if(opx<=l&&r<=opy) return sm[k];
int mid=(l+r)>>1;
if(lz[k]) down(k,l,mid,r);
return query(t[k][0],l,mid)+query(t[k][1],mid+1,r);
}
void change(int k,int l,int r,int v)
{
if(opx>opy||opy<l||opx>r) return;
if(opx<=l&&r<=opy) {sm[k]+=(v>0)?(r-l+1):(l-r-1),lz[k]+=v;return;}
int mid=(l+r)>>1;
if(lz[k]) down(k,l,mid,r);
if(opx<=mid) change(t[k][0],l,mid,v);
if(opy>=mid+1) change(t[k][1],mid+1,r,v);
sm[k]=sm[t[k][0]]+sm[t[k][1]];
}
void make()
{
int ls=1;
fo(i,1,m)
{
int c=st[i]-'a',p=ls;
ls=++n2,mx[ls]=i,ti[ls]=i,pt[i]=ls;
while(p&&!t1[p][c]) t1[p][c]=ls,p=fail[p];
if(p)
{
int q=t1[p][c];
if(mx[q]==mx[p]+1) fail[ls]=q;
else
{
fail[++n2]=fail[q];
fail[q]=fail[ls]=n2;
mx[n2]=mx[p]+1;
fo(j,0,25) t1[n2][j]=t1[q][j];
while(p&&t1[p][c]==q) t1[p][c]=n2,p=fail[p];
}
}
else fail[ls]=1;
}
}
struct LCT
{
int fn[L],f[L],r[L],t[L][2],d[L],lz[L];
void down(int k)
{
if(r[k])
{
swap(t[k][0],t[k][1]),fn[t[k][0]]=0,fn[t[k][1]]=1;
r[t[k][0]]^=r[k],r[t[k][1]]^=r[k];
r[k]=0;
}
lz[t[k][0]]=lz[t[k][1]]=lz[k];
}
void hb(int p,int x,int y)
{
if(x&&p!=-1) t[x][p]=y;
if(y) fn[y]=p,f[y]=x;
}
void rot(int k)
{
int fa=f[k],p=fn[k];
hb(p,fa,t[k][1-p]);
hb(fn[fa],f[fa],k);
hb(1-p,k,fa);
}
void splay(int k,int x)
{
d[d[0]=1]=k;
while(f[d[d[0]]]!=x&&f[d[d[0]]]!=0&&fn[d[d[0]]]!=-1) d[++d[0]]=f[d[d[0]-1]];
fod(i,d[0],1) down(d[i]);
while(f[k]!=x&&f[k]!=0&&fn[k]!=-1)
{
if(f[f[k]]==x||f[f[k]]==0||fn[f[k]]==-1) rot(k);
else if(fn[k]==fn[f[k]]) rot(f[k]),rot(k);
else rot(k);
}
}
void access(int k,int tc)
{
int p=k,k1=k;
splay(k,0);
fn[t[k][1]]=-1,t[k][1]=0;
while(k)
{
int fa=f[k];
if(lz[k]!=0) opx=lz[k]-mx[k]+1,opy=lz[k]-mx[fa],change(1,1,m,-1);
if(fa!=0)
{
splay(fa,0);
fn[t[fa][1]]=-1,hb(1,fa,k);
}
k1=k;k=fa;
}
lz[k1]=tc;
opx=tc-mx[p]+1,opy=tc-mx[k],change(1,1,m,1);
}
}T;
void read(int &x)
{
char ch=getchar();x=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
}
int main()
{
scanf("%s\n",ch1+1);
int nl=strlen(ch1+1),c=nl;
fo(i,1,nl/2)
{
if(nl%i==0)
{
bool pd=1;
fo(j,1,nl-i) if(ch1[j]!=ch1[j+i]) {pd=0;break;}
if(pd) {c=i;break;}
}
}
n=c;
fo(i,1,n) ch[i]=ch1[i];
m=0;
fo(j,0,2)
{
fo(i,1,n) st[m+i]=ch[i];
m+=n;
}
read(q);
fo(i,1,q)
{
int x,y;
read(x),read(y);
qs[i][2]=(y-x)/n;
qs[i][0]=x,qs[i][1]=y;
x=(x-1)%n+1,y=(y-1)%n+1;
if(y<x) y+=n;
if(qs[i][2]==0) ask[++q1]=(node){x,y,i,0};
else if(qs[i][2]==1) ask[++q1]=(node){x,y+n,i,1};
else ask[++q1]=(node){x,3*n,i,2};
}
sort(ask+1,ask+q1+1);
int j=1;
n1=1;
n2=1;
make();
fo(i,1,n2) T.f[i]=fail[i],T.fn[i]=-1;
build(1,1,m);
fo(i,1,m)
{
int k=pt[i];
T.access(k,i);
while(j<=q1&&ask[j].y<=i)
{
opx=ask[j].x,opy=i,s1[ask[j].w][ask[j].p]=query(1,1,m);
j++;
}
}
fo(i,1,q)
{
if(qs[i][2]<=1) printf("%lld\n",s1[i][qs[i][2]]);
else printf("%lld\n",s1[i][2]+(LL)(qs[i][1]-(qs[i][0]-1)/n*n-3*n)*(LL)n);
}
}