我明明可以编译压
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
#include<vector>
#define LL long long
#define pb push_back
#define PII pair<LL,LL>
#define mp make_pair
#define N 20100
#define M 510000
#define mmod 10000019
#define lowbit(x) (x&(-x))
using namespace std;
struct node{LL l,r,id;}q[N];
char ss[N],s[N];
LL cf[N];
LL g[N],ql,len,num,ans[N],lt[N];
int pre[mmod+10];
vector<PII> v[N];
void mnc()
{
g[1]=1;
LL k=1;
for(LL i=2;i<=len;i++)
{
LL p=k+g[k]-1;
LL l=g[2*k-i];
if(i+l<p) g[i]=l;
else
{
LL j=p-i;
if(j<1) j=1;
while(s[i+j]==s[i-j] && i+j<=len && i-j>=1) j++;
g[i]=j;
k=i;
}
}
for(LL i=1;i<=len;i++) v[i].clear();
num=0;
for(LL i=1;i<=len;i++)
{
LL h=s[i]-'a'+1;
if(s[i]!='|')
{v[i].pb(mp(pre[h]+1,i));pre[h]=i;}
for(LL j=1;j<=g[i]-1;j++)
{
h=((LL)(s[i-j]-'a'+1+h*27)+(LL)(s[i+j]-'a'+1)*(LL)cf[2*j])%mmod;
if(s[i+j]!='|')
{v[i+j].pb(mp(pre[h]+1,i-j));pre[h]=i-j;}
}
}
}
bool cmp(node x,node y)
{
if(x.r<y.r) return 1;
return 0;
}
void change(LL x,LL d)
{
for(LL i=x;i<=len;i+=lowbit(i)) lt[i]+=d;
}
LL find(LL x)
{
LL sum=0;
for(LL i=x;i;i-=lowbit(i)) sum+=lt[i];
return sum;
}
int main()
{
cf[0]=1;
for(LL i=1;i<N;i++) cf[i]=(cf[i-1]*27)%mmod;
LL z;
scanf("%I64d",&z);
while(z--)
{
memset(pre,0,sizeof(pre));
scanf("%s",ss+1);
len=strlen(ss+1);
scanf("%I64d",&ql);
for(int i=1;i<=ql;i++)
{
scanf("%I64d%I64d",&q[i].l,&q[i].r);
q[i].l=q[i].l*2-1;q[i].r=q[i].r*2-1;
q[i].id=i;
}
for(LL i=1;i<=len;i++)
{
s[i*2-1]=ss[i];
s[i*2]='|';
}
len*=2;
mnc();
sort(q+1,q+ql+1,cmp);
for(LL i=1;i<=len;i++) lt[i]=0;
LL j=1;
/*or(LL i=1;i<=len;i++)
{
LL siz=v[i].size();
printf("%I64d:\n",i);
for(LL j=0;j<siz;j++) printf("%I64d %I64d\n",v[i][j].first,v[i][j].second);
}*/
for(LL i=1;i<=len;i++)
{
LL siz=v[i].size();
for(LL k=0;k<siz;k++)
{
LL l=v[i][k].first,r=v[i][k].second;
change(l,1);
change(r+1,-1);
}
while(j<=ql && q[j].r==i)
{
ans[q[j].id]=find(q[j].l);
j++;
}
}
for(LL i=1;i<=ql;i++) printf("%I64d\n",ans[i]);
}
return 0;
}
