二维树状数组 回文

乍一看是区间DP+HASH，没错就是正解。
但我考试时任性的打了二维树状数组，挺快的。
对于每一个区间（N^2个）可表示为f[i][j]，满足二维树状数组的性质，
N^2扫每一个区间，插入。
查询：t[r][r]-t[l-1][r]-t[r][l-1]+t[l-1][l-1]就是了。

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int read()
{
    int sum=0,f=1;char x=getchar();
    while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
    while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}
    return sum*f;
}
char s[5005];
int n,m,f[5005][5005];
inline int low(int x){return x&(-x);}
inline void c(int x,int y)
{
    for(int i=x;i<=n;i+=low(i))
        for(int j=y;j<=n;j+=low(j))
            f[i][j]+=1;
}
inline int q(int x,int y)
{
    int s=0;
    for(int i=x;i>0;i-=low(i))
        for(int j=y;j>0;j-=low(j))
            s+=f[i][j];
    return s;
}
inline int Q(int x,int y){return q(y,y)-q(y,x-1)-q(x-1,y)+q(x-1,x-1);}
inline void check_1(int x)
{
    int l=x,r=x;
    while(l>0&&r<=n)
    {
        if(s[l]==s[r])c(l,r);
        else return;
        l--;r++;
    }
}
inline void check_2(int l,int r)
{
    while(l>0&&r<=n)
    {
        if(s[l]==s[r])c(l,r);
        else return;
        l--;r++;
    }
}
int main()
{
    scanf("%s",s+1);n=strlen(s+1);
    for(int i=1;i<=n;i++)check_1(i);
    for(int i=1;i<n;i++)check_2(i,i+1);
    m=read();int l,r;
    while(m--)
    {
        l=read();r=read();
        printf("%d
",Q(l,r));
    }
}