我太菜了。

首先考虑离线的套路,枚右端点,加入一个后缀,维护查询。

考虑一个正确性显然的暴力,每次枚举新的回文串 \(s[a,R]\),找到它上次最后出现的位置 \(s[c,d]\)

那么当 \(L\) 落在 \((c,a]\),答案会多 \(1\),回文树+线段树维护上次出现位置,以及枚举回文后缀。

这里有一个有关回文串 \(border\) 的性质:

  • 把一个回文串的所有 \(border\) 长度排序得到的序列,一定是 \(O(\log n)\) 个等差序列接成的。

  • 证明比较容易:

    考虑所有长度大于 \(\frac n 2\)\(border\) ,他们两两长度差值一定都是最小周期的倍数。

    因为左右对称的,所以就递归下去考虑前一半即可。

有这个性质之后就非常神奇,枚举回文后缀时,一个等差数列的贡献是连续一段区间,可以一起处理。

这样每次只要跳 \(O(\log n)\) 次就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define X first
#define Y second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=300005,maxe=maxn,P=1e9+7;
int N_PT,lst,Len[maxn],fail[maxn],ch[maxn][26];
int dif[maxn],dtail[maxn];
char s[maxn];
int newnode(int t){
Len[++N_PT]=t; memset(ch[N_PT],0,sizeof(ch[N_PT]));
return N_PT;
}
void Extend(int x){
int c=s[x]-'a';
int p=lst; while(s[x-Len[p]-1]!=s[x]) p=fail[p];
if(!ch[p][c]){
int np=newnode(Len[p]+2);
int t=fail[p]; while(s[x-Len[t]-1]!=s[x]) t=fail[t]; fail[np]=ch[t][c];
ch[p][c]=np;
dif[np]=Len[np]-Len[fail[np]];
dtail[np]=(dif[np]==dif[fail[np]]?dtail[fail[np]]:np);
}
lst=ch[p][c];
}
int N_seg,Ch[maxn*2][2],Max[maxn*2];
int Build(int L,int R){
int p=++N_seg;
if(L==R) return Max[p]=0,p;
int mid=(L+R)>>1;
Ch[p][0]=Build(L,mid); Ch[p][1]=Build(mid+1,R);
return p;
}
void maintain(int p){
Max[p]=max(Max[Ch[p][0]],Max[Ch[p][1]]);
}
void Update(int p,int L,int R,int pos,int val){
if(pos<L||R<pos) return;
if(L==R) return Max[p]=max(Max[p],val),void();
int mid=(L+R)>>1;
Update(Ch[p][0],L,mid,pos,val); Update(Ch[p][1],mid+1,R,pos,val);
maintain(p);
}
int Query(int p,int L,int R,int qL,int qR){
if(qR<L||R<qL) return 0;
if(qL<=L&&R<=qR) return Max[p];
int mid=(L+R)>>1;
return max(Query(Ch[p][0],L,mid,qL,qR),Query(Ch[p][1],mid+1,R,qL,qR));
}

int fir[maxn],nxt[maxe],son[maxe],tot;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int dfn[maxn],out[maxn],Tim;
void dfs(int x){
dfn[x]=++Tim;
for(int j=fir[x];j;j=nxt[j]) dfs(son[j]);
out[x]=Tim;
}
int n,m,ans;
int bit[maxn];
void Update(int x,int val){
for(;x<=n;x+=(x&-x)) bit[x]+=val;
}
int Query(int x){
int res=0;
for(;x;x-=(x&-x)) res+=bit[x];
return res;
}
vector< pair<int,int> > v[maxn];
int main(){
scanf("%d%d%s",&n,&m,s+1);
N_PT=-1; newnode(0); newnode(-1); s[0]=-1;
fail[0]=1; fail[1]=1; lst=0;
for(int i=1;i<=n;i++)
Extend(i);
for(int i=1;i<=m;i++){
int x,y; scanf("%d%d",&x,&y);
v[y].push_back(mp(x,i));
}
for(int i=0;i<=N_PT;i++) if(fail[i]!=i) add(fail[i],i);
dfs(1); Build(1,N_PT+1);
int p=1;
for(int i=1;i<=n;i++){
while(s[i]!=s[i-Len[p]-1]) p=fail[p]; p=ch[p][s[i]-'a'];
for(int j=p;j;j=fail[dtail[j]]){
int pos=Query(1,1,N_PT+1,dfn[j],out[j]); pos=max(1,pos-Len[j]+2);
Update(pos,1); Update(i-Len[dtail[j]]+2,-1);
}
Update(1,1,N_PT+1,dfn[p],i);
for(int j=0;j<v[i].size();j++)
(ans+=(LL)Query(v[i][j].X)*v[i][j].Y%P)%=P;
}
printf("%d\n",ans);
return 0;
}