题意
- 给(nle 10^5)个数，(mle 10^5)询问，每次询问区间(l_i,r_i)的所有回文串的价值和。
- 回文串的价值为该串所有数之和。
思路
- 将区间分成左右两个部分，左部分的回文中心会先超过左边界(l_i)，右半部分的回文中心则先超过右边界(r_i)。这两个可以看成同样的问题。
- 下面的做法只考虑左半区间。
- 假设回文中心(p)，半径为(L[p])，则(p)会和区间 ([p-L[p]+1,p]) 内的点构成回文串，对应回文串价值(前后对称，这边只写偶数长度的情况)为(2*(sum[p]-sum[x-1]),xin [p-L[p]+1,p])，(sum[i]) 表示前缀和。
- 若查询区间为 ([l_i, r_i])，则当回文中心处理到 (r_i) 对应的位置时，对应价值和为 ([l_i,r_i]) 的区间和，所以最后套个线段树即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define rep(i,l,r) for(int i=(l);i<(r);++i)
//-------
const int N = 1e5 + 7;
int n, m, c[N], sum[N], L[N << 1];
void manacher(int n, int a[], int l[]) {
l[0] = 1;
for (int i = 1, j = 0; i + 1 < n << 1; ++i) {
int p = i >> 1, q = i - p, r = (j + 1 >> 1) + l[j] - 1;
l[i] = r < q ? 0 : min(r - q + 1, l[(j << 1) - i]);
while (p - l[i] != -1 && q + l[i] != n && a[p - l[i]] == a[q + l[i]])
++l[i];
if (q + l[i] - 1 > r)
j = i;
}
}
struct SegTree {
#define ls ((t)<<1)
#define rs ((t)<<1|1)
int len[N << 2];
ll f[N << 2], g[N << 2], tot[N << 2], val[N << 2];
void build(int t, int l, int r) {
f[t] = g[t] = tot[t] = 0, len[t] = r - l + 1;
if (l == r) {
val[t] = sum[l - 1];
} else {
int z = (l + r) >> 1;
build(ls, l, z), build(rs, z + 1, r);
val[t] = val[ls] + val[rs];
}
}
inline void F(int t, ll add) {
f[t] += add, tot[t] += add * len[t];
}
inline void G(int t, ll add) {
g[t] += add, tot[t] += add * val[t];
}
inline void up(int t) {
tot[t] = tot[ls] + tot[rs];
}
void down(int t) {
if (f[t])
F(ls, f[t]), F(rs, f[t]), f[t] = 0;
if (g[t])
G(ls, g[t]), G(rs, g[t]), g[t] = 0;
}
void upd(int t, int l, int r, int L, int R, int V, char T) {
if (L <= l && r <= R) {
T == 'F' ? F(t, V) : G(t, V);
return ;
}
down(t);
int z = (l + r) >> 1;
if (L <= z)
upd(ls, l, z, L, R, V, T);
if (R > z)
upd(rs, z + 1, r, L, R, V, T);
up(t);
}
ll qry(int t, int l, int r, int L, int R) {
if (L <= l && r <= R)
return tot[t];
down(t);
int z = (l + r) >> 1;
ll ret = 0;
if (L <= z)
ret += qry(ls, l, z, L, R);
if (R > z)
ret += qry(rs, z + 1, r, L, R);
up(t);
return ret;
}
} seg;
ll ans[N];
vector<pair<pair<int, int>, int> > ql, qr;
void solve(vector<pair<pair<int, int>, int> > &q) {
manacher(n, c + 1, L + 1);
sort(q.begin(), q.end());
rep(i, 1, n + 1)
sum[i] = sum[i - 1] + c[i];
seg.build(1, 1, n);
int j = 0;
rep(i, 1, n << 1) {
int p = (i + 1) >> 1;
if (L[i]) {
seg.upd(1, 1, n, p - L[i] + 1, p, -2, 'G');
seg.upd(1, 1, n, p - L[i] + 1, p, sum[p] + (i & 1 ? sum[p - 1] : sum[p]), 'F');
}
while (j < sz(q) && q[j].first.first == i) {
ans[q[j].second] += seg.qry(1, 1, n, q[j].first.second, p);
++j;
}
}
}
int main() {
scanf("%d%d", &n, &m);
rep(i, 1, n + 1)
scanf("%d", &c[i]);
rep(i, 0, m) {
int l, r;
scanf("%d%d", &l, &r);
// left part
ql.pb(mp(mp((l + r) / 2 * 2 - 1, l), i));
// right part
qr.pb(mp(mp(2 * n - (l + r) / 2 * 2 , n + 1 - r), i));
}
solve(ql);
reverse(c + 1, c + 1 + n);
solve(qr);
rep(i, 0, m)
printf("%lld
", ans[i]);
return 0;
}