我现在感觉是评测机波动问题……随机 TLE 某几个点……

#include<stdio.h>
int min(int a,int b){return a<b?a:b;}
char s[200001];
int rk[200001],sa[200001],cnt[200001],tmp[200001],oldrk[200001],R[200001],root1[100001],root2[100001],tot;
struct{
    int s,l,r;
}tr[12000001];
int newnode(){return tr[++tot]={0,0,0},tot;}
int cpynode(int u){return tr[++tot]=tr[u],tot;}
int add(int u,int l,int r,int x){
    int v=cpynode(u);++tr[v].s;
    if(l==r)return v;
    int mid=l+r>>1;
    if(x<=mid)tr[v].l=add(tr[v].l,l,mid,x);
    else tr[v].r=add(tr[v].r,mid+1,r,x);
    return v;
}
int query(int u,int l,int r,int ql,int qr){
    if(!u)return 0;
    if(ql<=l&&r<=qr)return tr[u].s;
    int s=0,mid=l+r>>1;
    if(ql<=mid)s+=query(tr[u].l,l,mid,ql,qr);
    if(qr>mid)s+=query(tr[u].r,mid+1,r,ql,qr);
    return s;
}
void work(){
    int n,q;tot=0;
    scanf("%d%d %s",&n,&q,s);
    for(int i=1;i<=2*n;++i)++cnt[oldrk[i]=(i>n?s[2*n-i]:s[i-1])-'a'+1];
    for(int i=2;i<=26;++i)cnt[i]+=cnt[i-1];
    for(int i=1;i<=2*n;++i)sa[cnt[oldrk[i]]--]=i;
    for(int i=2;i<=26;++i)cnt[i]=0;
    rk[sa[1]]=1;
    for(int i=2,j=1;i<=2*n;++i){
        if(oldrk[sa[i-1]]!=oldrk[sa[i]])++j;
        rk[sa[i]]=j;
    }
    for(int l=1;l<n;l<<=1){
        auto check=[&n,&l](const auto&x){return x<=n-l||(n<x&&x<=2*n-l);};
        for(int i=1;i<=2*n;++i)oldrk[i]=rk[i];
        int p=0;
        for(int i=0;i<l;++i)tmp[++p]=n-i,tmp[++p]=2*n-i;
        for(int i=1;i<=2*n;++i)
            if((sa[i]<=n&&sa[i]>l)||sa[i]>n+l)tmp[++p]=sa[i]-l;
        for(int i=1;i<=p;++i)++cnt[rk[tmp[i]]];
        for(int i=2;i<=p;++i)cnt[i]+=cnt[i-1];
        for(int i=p;i>=1;--i)sa[cnt[oldrk[tmp[i]]]--]=tmp[i];
        for(int i=2;i<=p;++i)cnt[i]=0;
        p=rk[sa[1]]=1;
        for(int i=2;i<=2*n;++i){
            if(oldrk[sa[i-1]]!=oldrk[sa[i]]||(check(sa[i-1])?oldrk[sa[i-1]+l]:0)!=(check(sa[i])?oldrk[sa[i]+l]:0))
                ++p;
            rk[sa[i]]=p;
        }
    }
    for(int i=n;--i;)s[i*2]=s[i],s[i*2-1]='#';
    R[0]=1;
    for(int i=1,x=0,r=0;i<=2*(n-1);++i){
        if(i<=r)R[i]=min(r-i+1,R[2*x-i]);
        else R[i]=1;
        for(;R[i]<=i&&i+R[i]<=2*(n-1)&&s[i-R[i]]==s[i+R[i]];++R[i]);
        if(i+R[i]>r)r=i+R[i]-1,x=i;
    }
    int j=0;
    for(int i=1;i<n;i+=2,++j)root1[j+1]=add(root1[j],1,2*n,rk[2*n-i]);
    for(int i=0;i<n;i+=2,++j)root1[j+1]=add(root1[j],1,2*n,rk[2*n-i]);
    for(int i=j=1;i<2*(n-1);i+=2,++j)
        if(R[i]>1&&(i>=R[i]?s[i-R[i]]:0)>(i+R[i]<=2*(n-1)?s[i+R[i]]:0))
            root2[j]=add(root2[j-1],1,n,(i-R[i])/2+((i<R[i]||i+R[i]>2*(n-1))?1:2));
        else root2[j]=root2[j-1];
    for(int i,r;q--;){
        scanf("%d%d",&i,&r);
        int cnt1,cnt2=query(root2[i+r-1],1,n,1,i)-query(root2[i-1],1,n,1,i);
        if(i&1)cnt1=query(root1[(i+2*r-1)/2],1,2*n,rk[i]+1,2*n)-query(root1[(i-1)/2],1,2*n,rk[i]+1,2*n);
        else cnt1=query(root1[n/2+(i+2*r+1)/2],1,2*n,rk[i]+1,2*n)-query(root1[n/2+(i+1)/2],1,2*n,rk[i]+1,2*n);
        printf("%d\n",cnt1-cnt2);
    }
}
int main(){
    int t;
    for(scanf("%*d%d",&t);t--;work());
    return 0;
}