题目概述

给出一个序列，一个回文区间的权值是区间权值和，问 $[L,R]$ 中所有回文区间的权值和。

解题报告

刚开始想用回文自动机 $O(n\sqrt n)$ 暴搞，然后我自带大常数TLE了……

只需要考虑回文中心在 $[L,R]$ 的回文区间，但是回文中心向两端扩展的时候会碰到 $L$ 或 $R$ ，同时考虑两个端点很繁琐，我们可以把回文中心分成两半，那么左边会先碰到 $L$ ，右边会先碰到 $R$ 。

以左边为例，右边其实是一样的，考虑一个回文中心 $p$ 的贡献，假设 $p$ 向左能扩展到 $A$ ，那么权值就是：

$$ 2\sum_{i=A}^{p}(sum_p-sum_{i-1})-\sum_{i=A}^{p}a_p\\ \sum_{i=A}^{p}(2sum_p-a_p)-\sum_{i=A}^{p}2sum_{i-1} $$

把权值摊到 $[A,p]$ 中，就不需要考虑 $p$ 左边有没有碰到 $L$ 了，那么只需要线段树维护就行了。

但是这样处理会把后面没有出现过的回文中心算进来，所以我们离线，保证当前回文中心都会出现即可。

示例程序

因为Manacher加了辅助字符，所以每个区间都会被算两次，最后除以2就好了。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxq=100000;

int n,Q,a[maxn+5],p[maxn+5],sum[maxn+5];LL S[maxn+5];
int l[(maxn<<2)+5],r[(maxn<<2)+5],TB[(maxn<<2)+5];LL val[(maxn<<2)+5],TA[(maxn<<2)+5];
struct data {int l,r,ID;} q[maxq+5],now[maxq+5];LL ans[maxq+5];

inline void Manacher(int pos=0,int R=0){
    for (int i=1;i<=n;i++){
        if (i<R) p[i]=min(p[(pos<<1)-i],R-i); else p[i]=1;
        while (1<=i-p[i]&&i+p[i]<=n&&a[i-p[i]]==a[i+p[i]]) p[i]++;
        if (i+p[i]>R) pos=i,R=i+p[i];
    }
}
inline bool cmp(const data &a,const data &b) {return a.r<b.r;}
#define Pushup(p) (val[p]=val[(p)<<1]+val[(p)<<1|1])
void Build(int L,int R,int p=1){
    l[p]=L;r[p]=R;val[p]=TA[p]=TB[p]=0;if (L==R) return;int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);Pushup(p);
}
inline void AddtagA(int p,LL k) {val[p]+=k*(r[p]-l[p]+1);TA[p]+=k;}
inline void AddtagB(int p,int k) {val[p]+=(S[r[p]]-S[l[p]-1])*k;TB[p]+=k;}
inline void Pushdown(int p){
    if (TA[p]) AddtagA(p<<1,TA[p]),AddtagA(p<<1|1,TA[p]),TA[p]=0;
    if (TB[p]) AddtagB(p<<1,TB[p]),AddtagB(p<<1|1,TB[p]),TB[p]=0;
}
void AddA(int L,int R,int k,int p=1){
    if (L==l[p]&&r[p]==R) return AddtagA(p,k);int mid=l[p]+(r[p]-l[p]>>1);Pushdown(p);
    if (R<=mid) AddA(L,R,k,p<<1); else if (L>mid) AddA(L,R,k,p<<1|1);
    else AddA(L,mid,k,p<<1),AddA(mid+1,R,k,p<<1|1);Pushup(p);
}
void AddB(int L,int R,int k,int p=1){
    if (L==l[p]&&r[p]==R) return AddtagB(p,k);int mid=l[p]+(r[p]-l[p]>>1);Pushdown(p);
    if (R<=mid) AddB(L,R,k,p<<1); else if (L>mid) AddB(L,R,k,p<<1|1);
    else AddB(L,mid,k,p<<1),AddB(mid+1,R,k,p<<1|1);Pushup(p);
}
LL Ask(int L,int R,int p=1){
    if (L>R) return 0;if (L==l[p]&&r[p]==R) return val[p];int mid=l[p]+(r[p]-l[p]>>1);Pushdown(p);
    if (R<=mid) return Ask(L,R,p<<1);if (L>mid) return Ask(L,R,p<<1|1);return Ask(L,mid,p<<1)+Ask(mid+1,R,p<<1|1);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    int N;scanf("%d%d",&N,&Q);a[++n]=1e9;
    for (int i=1,x;i<=N;i++) scanf("%d",&x),a[++n]=x,a[++n]=1e9;Manacher();
    for (int i=1;i<=n;i++) sum[i]=sum[i-1]+(a[i]<1e9?a[i]:0),S[i]=S[i-1]+sum[i-1];
    for (int i=1;i<=Q;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].l=(q[i].l<<1)-1,q[i].r=(q[i].r<<1)+1;
    for (int i=1;i<=Q;i++) now[i].l=q[i].l,now[i].r=q[i].l+(q[i].r-q[i].l>>1),now[i].ID=i;
    Build(1,n);sort(now+1,now+1+Q,cmp);
    for (int i=1,j=1;i<=n&&j<=Q;i++){
        AddA(i-p[i]+1,i,(sum[i]<<1)-(a[i]<1e9?a[i]:0));AddB(i-p[i]+1,i,-2);
        while (j<=Q&&now[j].r==i) ans[now[j].ID]+=Ask(now[j].l,now[j].r),j++;
    }reverse(a+1,a+1+n);reverse(p+1,p+1+n);
    for (int i=1;i<=n;i++) sum[i]=sum[i-1]+(a[i]<1e9?a[i]:0),S[i]=S[i-1]+sum[i-1];
    for (int i=1;i<=Q;i++) now[i].l=n-q[i].r+1,now[i].r=n-(q[i].l+(q[i].r-q[i].l>>1)+1)+1,now[i].ID=i;
    Build(1,n);sort(now+1,now+1+Q,cmp);
    for (int i=1,j=1;i<=n&&j<=Q;i++){
        AddA(i-p[i]+1,i,(sum[i]<<1)-(a[i]<1e9?a[i]:0));AddB(i-p[i]+1,i,-2);
        while (j<=Q&&now[j].r==i) ans[now[j].ID]+=Ask(now[j].l,now[j].r),j++;
    }for (int i=1;i<=Q;i++) printf("%lld\n",ans[i]>>1);return 0;
}