HDU-5785 Interesting（Manacher算法+区间处理）

题目大意：给一个字符串，求所有相邻两回文子串的外侧下标之积的和

题目分析：另L[i]为所有以 i 为右端点的回文字串的左端点之和，同理，另R[i]表示所有以 i 为左端点的回文子串的右端点之和。显然，答案为sigma(L[i]*R[i+1]) 其中，1<=i<length(字符串)。求出L和R是关键。先用manacher算法处理出p数组，然后再求出L和R。求L和R的思想（非常巧妙）跟树状数组求区间和的思想差不多。不过，这道题如果用树状数组或线段树的话会超时。

参考代码：

# include<iostream>

# include<cstdio>

# include<cstring>

# include<algorithm>

using namespace std;

# define LL long long

const int mod=1000000007;

const int N=1000000;

char str[N+5];

char m[(N<<1)+5];

int p[(N<<1)+5];

LL addtag[2][N+5];

LL subtag[2][N+5];

LL addcnt[2][N+5];

LL subcnt[2][N+5];

LL val[2][N+5];

void manacher(char *ch)

{

	int len=strlen(ch+1);

	int cnt=0;

	m[cnt++]='@';

	m[cnt++]='#';

	for(int i=1;i<=len;++i){

		m[cnt++]=ch[i];

		m[cnt++]='#';

	}

	m[cnt]='\0';

	int id,mx=0;

	for(int i=1;i<cnt;++i){

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

		else p[i]=1;

		while(m[i-p[i]]==m[i+p[i]]) ++p[i];

		if(i+p[i]>mx){

			mx=i+p[i];

			id=i;

		}

	}

}

void update(int id,int l,int r,int a)

{

	addtag[id][l]+=a;

	addtag[id][l]%=mod;

	++addcnt[id][l];

	subtag[id][r+1]+=a-r+l;

	subtag[id][r+1]%=mod;

	++subcnt[id][r];

}

void pushDown(int n)

{

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

		if(addcnt[0][i]){

			val[0][i]+=addtag[0][i];

			val[0][i]%=mod;

			addtag[0][i+1]+=addtag[0][i]-addcnt[0][i];

			addtag[0][i+1]%=mod;

			addcnt[0][i+1]+=addcnt[0][i];

		}

		if(subcnt[0][i]){

			val[0][i]-=subtag[0][i];

			val[0][i]%=mod;

			subtag[0][i+1]+=subtag[0][i]-subcnt[0][i];

			subtag[0][i+1]%=mod;

			subcnt[0][i+1]+=subcnt[0][i];

		}

		if(addcnt[1][i]){

			val[1][i]+=addtag[1][i];

			val[1][i]%=mod;

			addtag[1][i+1]+=addtag[1][i]-addcnt[1][i];

			addtag[1][i+1]%=mod;

			addcnt[1][i+1]+=addcnt[1][i];

		}

		if(subcnt[1][i]){

			val[1][i]-=subtag[1][i];

			val[1][i]%=mod;

			subtag[1][i+1]+=subtag[1][i]-subcnt[1][i];

			subtag[1][i+1]%=mod;

			subcnt[1][i+1]+=subcnt[1][i];

		}

	}

}

int main()

{

	while(~scanf("%s",str+1))

	{

		manacher(str);

		memset(val,0,sizeof(val));

		memset(addtag,0,sizeof(addtag));

		memset(subtag,0,sizeof(subtag));

		memset(addcnt,0,sizeof(addcnt));

		memset(subcnt,0,sizeof(subcnt));

		for(int i=1;m[i];++i){

			if(i&1){

				if(p[i]==1) continue;

				update(0,i/2+1,i/2+p[i]/2,i/2);

				update(1,i/2-p[i]/2+1,i/2,i/2+p[i]/2);

			}else{

				int id=i/2;

				int l=(p[i]-1)/2;

				update(0,id,id+l,id);

				update(1,id-l,id,id+l);

			}

		}

		int n=strlen(str+1);

		pushDown(n);

		LL ans=0;

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

			ans+=val[0][i]*val[1][i+1];

			ans%=mod;

		}

		while(ans<0) ans+=mod;

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

	}

	return 0;

}