[Manacher+bit]Palindrome

https://nanti.jisuanke.com/t/15428

题目大意：离散表示的字符串，求其最长回文串长度。

解题关键：若只用Manacher算法，在统计sum时会超时，所以加一个树状数组来维护前n项和，即可AC。

　　注意进行Manacher时，i是从1开始的，不要小也不要大。

n天后更新：以前一直没搞清离线与动态维护的区别，今天终于理解了，此题可以开始直接离线求前n项和，因为以后不再改变，所以此题不需要bit维护。直接用一个数组统计一下前n项和即可。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 struct node{

     ll num;

     char ch;

 }s[];

 ll p[],sum[],bit[];

 ll t,n,a,k,id,maxlen,tt;

 ll read(ll i){

     ll res=;

     while(i){

         res+=bit[i];

         i-=i&-i;

     }

     return res;

 }

 void add1(ll i,ll x){

     while(i<){

         bit[i]+=x;

         i+=i&-i;

     }

 }

 int main(){

     scanf("%lld",&t);

     while(t--){

         memset(p,,sizeof p);

         memset(bit,,sizeof bit);

         memset(s,,sizeof s);

         memset(sum,,sizeof sum);

         scanf("%lld",&n);

         k=;

         for(int i=;i<n;i++){

             k++;

             //cin>>s[k].num>>s[k].ch;

             scanf("%lld %c",&s[k].num,&s[k].ch);

             tt=s[k].num;

             if(s[k].ch==s[k-].ch){

                 s[k-].num+=s[k].num;

                 k--;

             }

             add1(k,tt);

         }

         id=,maxlen=;

         s[].ch='*',s[k+].ch='#';

         for(int i=;i<=k;i++){

             if(p[id]+id>i) p[i]=min(p[*id-i],p[id]+id-i);

             else p[i]=;

             while(s[i-p[i]].ch==s[i+p[i]].ch&&s[i-p[i]].num==s[i+p[i]].num)++p[i];

             if(p[i]+i>p[id]+id) id=i;

             sum[i]=read(i+p[i]-)-read(i-p[i]);

             if(s[i-p[i]].ch==s[i+p[i]].ch) sum[i]+=*min(s[i-p[i]].num,s[i+p[i]].num);

             maxlen=max(maxlen,sum[i]);

         }

         printf("%lld\n",maxlen);

     }

     return ;

 }

巴特西

[Manacher+bit]Palindrome

最新文章

热门文章