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);
}
}