HDU6230-Palindrome

题目连接
题目大意：定义一种 $one-and-half$one−and−half 回文串，其长度为 $3n-2$3n−2 ，满足 $s\left[i\right]=s[2n-i]=s[2n-2+i],1\le i\le n$s[i]=s[2n−i]=s[2n−2+i],1≤i≤n 。输入一个长度为n $(n\le 5e5)$(n≤5e5)的字符串，求其有多少个子串是这样的回文串。
这是一种有两个对称轴的回文串，我们可以枚举左边的对称轴，然后看有多少个右边的对称轴能够配对。
先采用马拉车Manacher算法预处理得到p[i]。由于这道题目的 $one-and-half$one−and−half串是两个奇数回文串拼成的，所以马拉车算法无需考虑偶数情况。接下来在给每个对称轴向右寻找配对时，需要注意彼此的最大回文串需互相包含，且大小均大于1。于是我们可以不断维护一个数据结构，用来储存包含当前点i（左对称轴）的右对称轴，然后只需要看 i 的右边最远延申的位置，对该数据结构中 $[i+1,i+p[i]-1]$[i+1,i+p[i]−1]区间中的右对称轴数量求和即可。这个数据结构可以采用树状数组，因为我们只需要两个操作：1、单点修改（+1） 2、区间求和

#include<iostream>
#include<string>
#include<vector>
using namespace std;
#define ll long long
int n;
const int maxn=5e5+4;
int bit[maxn];
int lowbit(int i){
    return i&-i;
}
void add(int id,int val){
    while(id<=n){
        bit[id]+=val;
        id+=lowbit(id);
    }
}
int sum(int id){
    int res=0;
    while(id>0){
        res+=bit[id];
        id-=lowbit(id);
    }
    return res;
}
vector<int> mp[maxn];
int p[maxn];
char s[maxn];
int t;
string str;
int main(){
    cin>>t;
    while(t--){
        cin>>str;
        n=str.length();
        for(int i=1;i<=n;i++){
            mp[i].clear();
            bit[i]=p[i]=0;
        }
        for(int i=1,l=1,r=0;i<=n;i++){
            int k=(i>r?1:min(p[l+r-i],r-i+1));
            while(i+k<=n&&i-k>0&&str[i+k-1]==str[i-k-1]){   //逻辑下标从1开始，物理下标从0开始
                k++;
            }
            p[i]=k--;
            if(i+k>r){
                r=i+k;
                l=i-k;
            }
        }
        for(int i=n;i>0;i--){
            if(p[i]>1)
                mp[i-p[i]+1].push_back(i);
        }
        ll res=0;
        for(int i=1;i<n-1;i++){
            for(int j=0;j<mp[i].size();j++){
                add(mp[i][j],1);
            }
            if(p[i]==1)
                continue;
            res+=(ll)sum(min(n,i+p[i]-1))-(ll)sum(i);
        }
        cout<<res<<endl;
    }
    return 0;
}