HDU 6230 Palindrome CCPC2017 Harbin（Manacher+樹狀數組+離線處理）

Palindrome

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Total Submission(s): 20    Accepted Submission(s): 9

Problem Description

Alice like strings, especially long strings. For each string, she has a special evaluation system to judge how elegant the string is. She defines that a stringS[1..3n−2](n≥2) is one-and-half palindromic if and only if it satisfies S[i]=S[2n−i]=S[2n+i−2](1≤i≤n).For example, abcbabc is one-and-half palindromic string, and abccbaabc is not. Now, Alice has generated some long strings. She ask for your help to find how many substrings which is one-and-half palindromic.

Input

The first line is the number of test cases. For each test case, there is only one line containing a string(the length of strings is less than or equal to500000), this string only consists of lowercase letters.

Output

For each test case, output a integer donating the number of one-and-half palindromic substrings.

Sample Input

1

ababcbabccbaabc

Sample Output

Hint

Source

2017中國大學生程式設計競賽-哈爾濱站-重制賽（感謝哈理工）

        在哈爾濱的第一場比賽真的是像發瘋了一樣，在水題上糾結了近四個小時……當時真菜……

        現在回過頭來看，這道題目還是非常的巧妙的。首先，我們要清楚的明白，這個回文的性質，例如：abcbabc，有兩個對稱中心'c'和'a'，然後第二個對稱中心的長度要恰好為兩個對稱中心的距離。轉換成符号表示就是，i<j，j-i==len[j]且j-i<=len[i]。更确切的說就是，第二個對稱中心要落在第一個對稱的範圍内，而且第二個對稱中心的長度要恰好為兩個對稱中心的距離。

#include<bits/stdc++.h>
#define N 1001000
#define LL long long

using namespace std;

struct node{int x,id;} a[N];
int n,p[N],rl[N];
char s[N];

struct BinaryIndexedTree
{
    LL c[N];

    inline void init()
    {
        memset(c,0,sizeof(c));
    }

    inline int lowbit(int x)
    {
        return x&-x;
    }

    inline void update(int x,int k)
    {
        while (x<=n*2)
        {
            c[x]+=k;
            x+=lowbit(x);
        }
    }

    inline LL getsum(int x)
    {
        LL ans=0;
        while (x>0)
        {
            ans+=c[x];
            x-=lowbit(x);
        }
        return ans;
    }
} BIT;

void manacher()
{
    int len=strlen(s);
    for(int i=len;i>=0;--i)
        s[i+i+1]=s[i],s[i+i]='#';
    int id,mx=0;
    for(int i=1;i<len+len+1;++i)
    {
        if (mx>i) p[i]=min(p[2*id-i],mx-i); else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]]&&i-p[i]>=0&&i+p[i]<len+len+1)++p[i];
        if(i+p[i]>mx) id=i,mx=p[i]+i;
        if (s[i]!='#') rl[(i+1)/2]=(p[i]-1)/2;
    }
}

bool cmp(node a,node b)
{
    return a.x>b.x;
}

int main()
{
    int T_T;
    cin>>T_T;
    while(T_T--)
    {
        LL ans=0;
        BIT.init();
        scanf("%s",s);
        n=strlen(s); manacher();
        for(int i=1;i<=n;i++)
        {
            a[i].x=rl[i]-i;
            a[i].id=i;
        }
        int j=-1;
        sort(a+1,a+1+n,cmp);                        //從大到小排序
        for(int i=1;i<=n;i++)
        {
            while(a[i].x<j&&j>=-n)                    //當沒有可以更新的點的時候，進行查詢
            {
                ans+=BIT.getsum(-j+rl[-j])-BIT.getsum(-j);        //查詢區間内可行的j的數量
                j--;
            }
            BIT.update(a[i].id,1);                    //更新滿足條件的點
        }
        while(j>=-n)                            //處理尾巴
        {
            ans+=BIT.getsum(-j+rl[-j])-BIT.getsum(-j);
            j--;
        }
        printf("%I64d\n",ans);
    }
}