如果我让你查回文你还爱我吗

[如果我让你查回文你还爱我吗]

思路

对中心进行划分，这样子就只需要考虑一边就可以了
然后用树状数组或线段树对差分数组进行维护

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M=4e5+5;

int n,q;
struct BIT {
    int c1[M],c2[M];
    void init() {
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
    }
    int lowbit(int x){return x&-x;}
    void add(int x,int v) {
        for(int i=x;i<=n;i+=lowbit(i))
            c1[i]+=v,c2[i]+=v*x;
    }
    void range_add(int l,int r,int v) {
        add(l,v);add(r+1,-v);
    }
    int query(int x) {
        int ans=0;
        for(int i=x;i;i-=lowbit(i))
            ans+=(x+1)*c1[i]-c2[i];
        return ans;
    }
    int range_query(int l,int r) {
        return query(r)-query(l-1);
    }
}TR;

char s[M];
int p[M];
void Manacher(string t) {
    s[0]='!',s[1]='#';
    int cnt=1;
    for(auto x:t) {
        s[++cnt]=x;
        s[++cnt]='#';
    }
    n=cnt;
    for(int i=1,r=1,mid=1;i<=n;i++) {
        if(i<r)p[i]=min(p[2*mid-i],p[mid]+mid-i);
        while(s[i-p[i]]==s[i+p[i]])p[i]++;
        if(i+p[i]>r)r=i+p[i],mid=i;
    }
}

vector<pair<int,int>>ql[M],qr[M];
int ans[M];
signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>q;
    string t;cin>>t;
    Manacher(t);
    for(int i=1;i<=q;i++) {
        int l,r;
        cin>>l>>r;
        ans[i]-=r-l+2;
        l=l*2-1,r=r*2+1;
        int mid=(l+r)/2;
        ql[mid].push_back({i,l});
        qr[mid+1].push_back({i,r});
    }
    for(int i=1;i<=n;i++) {
        TR.range_add(i-p[i]+1,i,1);
        for(auto [x,y]:ql[i])
            ans[x]+=TR.range_query(y,i);
    }
    TR.init();
    for(int i=n;i>=1;i--) {
        TR.range_add(i,i+p[i]-1,1);
        for(auto [x,y]:qr[i])
            ans[x]+=TR.range_query(i,y);
    }
    for(int i=1;i<=q;i++)cout<<ans[i]/2<<'\n';
    //为什么会统计两次
    //这里不是很懂呀
    return 0;
}
//为什么要统计两次呢