对于给出的串 \(S\)，将其拓展成 \(S+\) 特殊字符 \(+rev(S)\) ，求出其后缀数组。
那么对于一个子串 \([l,r]\)，合法的必要条件是 \(l\) 的后缀在后缀数组的排名小于 \(r\) 的前缀的排名。
之所以是必要条件，是因为会记入一些 \([l,r]\) 是回文串且 \(l\) 的排名小的情况。
具体而言，这种情况会发生，当且仅当：我们求出向左右两边拓展直到两边字符所能拓展的最长回文串，那么要求这个回文串左右两边不为空，且右边的字典序小于左边的。
我们考虑用第一种情况减掉第二种情况。
第一种情况求出后缀数组之后是个简单的二维数点，第二种考虑枚举一个回文中心，那么只有以其为中心的最长回文串是有用的，如果其满足第二个情况，也可以列出一个二维数点的式子，都可以离线树状数组解决。
复杂度 \(O((n+m)\log n)\) 。
因为不会后缀数组，所以采用的是求出后缀树然后再建出后缀数组的方式。
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+7;
int n,q;
char s[N];
int tr[N][27],son[N][27],len[N],fa[N],pos[N],key[N];
int tot=1,last=1;
void init()
{
for(int i=1;i<=tot;i++)
{
len[i]=fa[i]=pos[i]=key[i]=0;
for(int c=0;c<27;c++)
tr[i][c]=son[i][c]=0;
}
tot=last=1;
}
void copy(int a,int b)
{
len[a]=len[b];
fa[a]=fa[b];
pos[a]=pos[b];
for(int c=0;c<27;c++)
tr[a][c]=tr[b][c];
}
void Extend(int c,int x)
{
int p=last,np=last=++tot;
len[np]=len[p]+1;
pos[np]=x;
key[np]=1;
while(p&&!tr[p][c])
{
tr[p][c]=np;
p=fa[p];
}
if(!p)fa[np]=1;
else
{
int q=tr[p][c];
if(len[q]==len[p]+1)fa[np]=q;
else
{
int nq=++tot;
copy(nq,q);
len[nq]=len[p]+1;
fa[np]=fa[q]=nq;
while(p&&tr[p][c]==q)
{
tr[p][c]=nq;
p=fa[p];
}
}
}
}
int sa[N],rk[N],top=0;
void getsa(int x)
{
if(key[x])
{
sa[++top]=pos[x];
rk[pos[x]]=top;
}
for(int c=0;c<27;c++)
if(son[x][c])getsa(son[x][c]);
}
char str[N];
int h[N],range[N];
void manacher()
{
int p=0,r=0,c=0;
for(int i=1;i<=top;i++)h[i]=0;
for(int i=1;i<=top;i++)
{
if(i<=r)h[i]=min(h[2*p-i],r-i+1);
while(str[i-h[i]]==str[i+h[i]])h[i]++;
if(str[i]>='a'&&str[i]<='z') c++;
if(str[i]=='#'&&i>2) range[c]=h[i]/2;
if(i+h[i]-1>r)
{
p=i;
r=i+h[i]-1;
}
}
}
struct BIT
{
int c[N],m;
void clr(int _m)
{
for(int i=1;i<=m;i++)c[i]=0;
m=_m;
}
void upd(int x,int v)
{
for(int i=x;i<=m;i+=i&-i)
c[i]+=v;
}
int ask(int x)
{
int res=0;
for(int i=x;i;i-=i&-i)
res+=c[i];
return res;
}
int qry(int l,int r){return ask(r)-ask(l-1);}
}C[2],D;
struct Query
{
int id,x,r,op;
};
vector<Query> Q[N],Q2[N];
int ans[N];
void solve()
{
scanf("%d %d",&n,&q);
scanf("%s",s+1);
init();
int val=0;
for(int i=1;i<=n;i++)s[++val]=s[i];
s[++val]='a'+26;
for(int i=n;i>=1;i--)s[++val]=s[i];
for(int i=1;i<=val;i++)Extend(s[i]-'a',i);
for(int i=2;i<=tot;i++)son[fa[i]][s[pos[i]-len[fa[i]]]-'a']=i;
top=0;getsa(1);
top=0;
str[++top]='$';
str[++top]='#';
for(int i=1;i<=n;i++)str[++top]=s[i],str[++top]='#';
str[++top]='&';
manacher();
C[0].clr(val);C[1].clr(val);D.clr(n);
for(int i=1;i<=n;i++)Q[i].clear(),Q2[i].clear();
for(int i=1;i<=q;i++)
{
int x,r;
ans[i]=0;
scanf("%d %d",&x,&r);
int u=n-x+2+n;
//int res=0;
Q[x-1].push_back((Query){i,u,r,-1});
Q[x+2*r-1].push_back((Query){i,u,r,1});
Q2[x-1].push_back((Query){i,x,r,-1});
Q2[x+r-1].push_back((Query){i,x,r,1});
// for(int i=1;i<=r;i++) if(rk[x+2*i-1]>rk[u])res++;
// for(int i=x;i<=n;i++)
// {
// int pl=i-range[i]+1,pr=i+range[i];
// if(pl>1&&pr<n&&pl<=x&&i<=x+r-1) res-=(s[pl-1]>s[pr+1]);
// }
// printf("%d\n",res);
}
for(int i=1;i<=n;i++)
{
C[i&1].upd(rk[i],1);
int pl=i-range[i]+1,pr=i+range[i];
if(pl>1&&pr<n&&s[pl-1]>s[pr+1]) D.upd(pl,1);
for(auto U:Q[i]) ans[U.id]+=1ll*U.op*C[i&1].qry(rk[U.x]+1,val);
for(auto U:Q2[i]) ans[U.id]-=1ll*U.op*D.ask(U.x);
}
for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}
int main()
{
int tp,T;
cin>>tp>>T;
while(T--)
{
solve();
}
return 0;
}