HDU5785 Interesting题解

· · 个人记录

题面

前置知识：manacher，差分

题解：

首先我们尝试把所求变形

根据乘法分配律，我们知道

x_1*y_1+x_1*y_2+x_2*y_1+x_2*y_2=(x_1+x_2)*(y_1+y_2)

那么同理，可以令:

$sum[1][i]$表示以$i$起始的回文串的结尾位置的和 那么我们需要在$O(n)$的时间内求出$sum[0][i]$与$sum[1][i]

考虑用manacher将回文半径(p数组)求出

那么可以考虑中间为i，半径为p[i]的最长回文串对答案的贡献

(这里只考虑sum[0][i]，sum[1][i]同理)

那么[i-p[i]+1, i+p[i]-1]就是回文串
    故sum[0][i+p[i]-1]就该加上i-p[i]+1；
则  [i-p[i]+2, i+p[i]-2]也是回文串
    sum[0][i+p[i]-2]就该加上i-p[i]+2

以此类推，可以发现，该串对答案的贡献成一个等差数列。

也就是：

对于sum[0][i]数组要在[i, i+p[i]-1]区间上依次加上一个末项为i-p[i]+1且公差为-1的等差数列

接下来考虑如何修改与统计。

由于需要O(n)时间，考虑差分的方式。

由于各个位置上加的值并不一样，所以与正常的差分不同，我们需要存2个值：

num: 传统差分中存储的修改值

cnt: 被多少个要修改的区间覆盖

并且加标记与减标记我们需要开两个数组分别存。

(下面同样只考虑加标记，减标记同理)

当然由于是等差数列，所以我们需要将标记依次向下传递

num[i]+=num[i-1]-cnt[i-1]，cnt[i]+=cnt[i-1]

然后我们只需要O(1)修改，O(n)查询，并且在查询过程中下传即可。

(PS：很多需注意的细节请结合代码)。

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
const long long mod=1e9+7;
char s[1000005],snew[2000005];
int p[2000005];
struct node{
    long long num,cnt;
}add[2][1000005],sub[2][1000005];
long long sum[2][1000005],ans;
inline void update(int flag,int l,int r,int k)
{
    add[flag][l].num=(add[flag][l].num+k)%mod,add[flag][l].cnt++;
    sub[flag][r+1].num=(sub[flag][r+1].num+k-(r-l))%mod,sub[flag][r].cnt++;
}   
inline void query()
{
    for (register int i=1;s[i];++i)
        {
        if (add[0][i].cnt)
           {
           sum[0][i]=(sum[0][i]+add[0][i].num)%mod;
           add[0][i+1].num=(add[0][i+1].num+add[0][i].num-add[0][i].cnt)%mod,add[0][i+1].cnt+=add[0][i].cnt;
           }
        if (add[1][i].cnt)
           {
           sum[1][i]=(sum[1][i]+add[1][i].num)%mod;
           add[1][i+1].num=(add[1][i+1].num+add[1][i].num-add[1][i].cnt)%mod,add[1][i+1].cnt+=add[1][i].cnt;
           }
        if (sub[0][i].cnt)
           {
           sum[0][i]=(sum[0][i]-sub[0][i].num)%mod;
           sub[0][i+1].num=(sub[0][i+1].num+sub[0][i].num-sub[0][i].cnt)%mod,sub[0][i+1].cnt+=sub[0][i].cnt;
           }
        if (sub[1][i].cnt)
           {
           sum[1][i]=(sum[1][i]-sub[1][i].num)%mod;
           sub[1][i+1].num=(sub[1][i+1].num+sub[1][i].num-sub[1][i].cnt)%mod,sub[1][i+1].cnt+=sub[1][i].cnt;
           }
        }
}
inline void ready()
{
    snew[0]='$',snew[1]='#';
    int j=1;
    for (register int i=1;s[i];++i)
        snew[++j]=s[i],snew[++j]='#';
    snew[++j]=0;
}
inline void manacher()
{
    int r=0,mid=0;
    for (register int i=1;snew[i];++i)
        {
        p[i]=(i<r?min(p[mid*2-i],r-i):1);
        while (snew[i-p[i]]==snew[i+p[i]])
              p[i]++;
        if (i+p[i]>r)
           r=i+p[i],mid=i;
        }
}
inline void clear()
{
    ans=0;
    memset(sum,0,sizeof(sum));
    memset(add,0,sizeof(add));
    memset(sub,0,sizeof(sub));
}
int main(){
//  freopen("B.in","r",stdin);
//  freopen("B.out","w",stdout);
    while (~scanf("%s",s+1))
          {
          clear();
          ready();
          manacher();
          for (register int i=1;snew[i];++i)
              {
              if (i&1)
                 {
                 if (p[i]/2==0)
                    continue;
                 update(0,i/2-p[i]/2+1,i/2,i/2+p[i]/2);
                 update(1,i/2+1,i/2+p[i]/2,i/2);
                 }
              else
                 {
                 update(0,i/2-p[i]/2+1,i/2,i/2+p[i]/2-1);
                 update(1,i/2,i/2+p[i]/2-1,i/2);
                 }
              }
          query();
          for (register int i=1;s[i]&&s[i+1];++i)
              ans=(ans+sum[0][i+1]*sum[1][i])%mod;
          printf("%lld\n",(ans<0?ans+mod:ans));
          }
    return 0;
}