[2019寒假集训day1]三元组(Manacher+差分)

题面

题解

被题解坑到自闭系列…
不得不说能把一道这么简单的题写的如此好理解也是一种能力

明显首先需要Manacher，然后得到最大半径$p_i$,发现对答案的贡献是一个等差序列。
于是我们可以用6个数组维护等差序列。
分别是$ls{1}_i,ls{2}_i,ls{3}_i,rs{1}_i,rs{2}_i,rs{3}_i$。
分别代标从$i$点开始的首项之和,公差之和，与公差之和的和
以及从$i$点结束的首项之和,公差之和，与公差之和的和
这里指的公差之和的和就是首先为1得等差序列，统计答案时加上首项之和即可。
按照如下规则差分

int l=(i-p[i])/2,r=(i+p[i]-1)/2,mid=(i-1)/2;
ls1[l]+=(r+1),ls1[mid+1]-=(r+1);
ls2[l+1]--,ls2[mid+1]++;
ls3[mid+1]+=(mid-l);
mid=i/2;
rs1[mid]+=(i+1)/2,rs1[r+1]-=(i+1)/2;
rs2[mid+1]--,rs2[r+1]++;
rs3[r+1]+=(r-mid);

然后答案就是$(ls1[i]+ls3[i])?(rs1[i?1]+rs3[i?1])$。
细节超多…
复杂度:$O(n)$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 1000000
#define LL long long
#define MOD 1000000007
int T,len,n;
char LS[MAXN*2+5],s[MAXN*2+5];
int p[MAXN*2+5];
LL ls1[MAXN+5],ls2[MAXN+5],ls3[MAXN+5],rs1[MAXN+5],rs2[MAXN+5],rs3[MAXN+5],ans;
void Init()
{
    s[0]='#';for(int i=2;i<=len*2;i+=2){
    s[i-1]=LS[i/2];s[i]='#';}s[len*2]='#';
}
void prefix_s(LL *s1,LL* s2,LL *s3,int p)
{
    s1[p]+=s1[p-1];s1[p]%=MOD;s2[p]+=s2[p-1];s2[p]%=MOD;s3[p]+=s3[p-1]+s2[p];s3[p]%=MOD;
}
void Manacher()
{
    Init();len=strlen(s);int pos,mr=0;for(int i=1;i<len;i++){
    if(i<mr)p[i]=min(p[pos*2-i],mr-i);else p[i]=0;while(i+p[i]+1<=len&&i-p[i]-1>=0&&s[i-p[i]-1]==s[i+p[i]+1])p[i]++;if(mr<p[i]+i)mr=p[i]+i,pos=i;if(p[i]!=0){
    int l=(i-p[i])/2,r=(i+p[i]-1)/2,mid=(i-1)/2;ls1[l]+=(r+1),ls1[mid+1]-=(r+1);ls2[l+1]--,ls2[mid+1]++;ls3[mid+1]+=(mid-l);mid=i/2;rs1[mid]+=(i+1)/2,rs1[r+1]-=(i+1)/2;rs2[mid+1]--,rs2[r+1]++;rs3[r+1]+=(r-mid);}}return ;
}
int main()
{
    freopen("triple.in","r",stdin);freopen("triple.out","w",stdout);scanf("%d",&T);while(T--){
    scanf("%s",LS+1);len=n=strlen(LS+1);memset(s,0,sizeof(s));for(int i=0;i<=n+1;i++)ls1[i]=ls2[i]=ls3[i]=rs1[i]=rs2[i]=rs3[i]=0;p[0]=0;ans=0;Manacher();for(int i=1;i<=n;i++){
    prefix_s(ls1,ls2,ls3,i);prefix_s(rs1,rs2,rs3,i);ans=(ans+((ls1[i]+ls3[i])%MOD)*((rs1[i-1]+rs3[i-1])%MOD)%MOD)%MOD;}printf("%lld\n",ans);}
}