2018-06-06 20:31:06

Luogu-P4555

Blog上阅读效果更好

思路

1. 区间加 $a_0 = 1, d = 1$ 的等差数列
2. 单点求值。

代码

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

const int MAXN = 3e5, INF = 0x3f3f3f3f;
const ull base = 1313;
int n, ans, pre[MAXN + 10], suf[MAXN + 10];
char s0[MAXN + 10], s[MAXN + 10], *ptr = &s[1];
ull powbase[MAXN + 10], hval[MAXN + 10], hrev[MAXN + 10];

struct SegTree {
#define lc(o) ((o) << 1)
#define rc(o) ((o) << 1 | 1)
int sumv[(MAXN + 10) << 2], setv[(MAXN + 10) << 2];

SegTree() { fill(setv, setv + ((MAXN + 10) << 2), -INF); }

void maintain(int o, int l, int r) {
if(l != r) sumv[o] = sumv[lc(o)] + sumv[rc(o)];
if(setv[o] != -INF) sumv[o] = setv[o] * (r - l + 1);
}

void build_tree(int o, int l, int r) {
if(l == r)
setv[o] = -l;
else {
int mid = (l + r) >> 1;
build_tree(lc(o), l, mid);
build_tree(rc(o), mid + 1, r);
}
maintain(o, l, r);
}

void cover(int o, int l, int r, int ql, int qr, int val) {
if(ql > qr) return;
if(ql <= l && r <= qr)
setv[o] = max(setv[o], val);
else {
int mid = (l + r) >> 1;
if(ql <= mid) cover(lc(o), l, mid, ql, qr, val);
if(qr >= mid + 1) cover(rc(o), mid + 1, r, ql, qr, val);
}
maintain(o, l, r);
}

int query(int o, int l, int r, int p) {
maintain(o, l, r);
if(l == r)
return sumv[o];
else {
int mid = (l + r) >> 1;
if(p <= mid)
return max(setv[o], query(lc(o), l, mid, p));
else
return max(setv[o], query(rc(o), mid + 1, r, p));
}
}
#undef lc
#undef rc
} seg1, seg2;

inline ull get_hash(ull h[], int l, int r) {
return h[r] - h[l - 1] * powbase[r - l + 1];
}

inline int odd_palindrome(int p) {  // p是回文中心
int l = 1, r = n + 1;
while(l < r) {
int mid = (l + r) >> 1;
if(mid <= max(p, n - p + 1) &&
get_hash(hval, p, p + mid - 1) ==
get_hash(hrev, n - p + 1, n - p + mid))
l = mid + 1;
else
r = mid;
}
return l - 1;
}

int main() {
scanf("%s", &s0[1]);
n = strlen(s0 + 1);
*(ptr++) = '#';
for(int i = 1; i <= n; i++) {
*(ptr++) = s0[i];
*(ptr++) = '#';
}
n = strlen(s + 1);

powbase[0] = 1;
for(int i = 1; i <= MAXN; i++) powbase[i] = powbase[i - 1] * base;
for(int i = 1; i <= n; i++) hval[i] = hval[i - 1] * base + s[i];
for(int i = 1; i <= n; i++) hrev[i] = hrev[i - 1] * base + s[n - i + 1];

seg1.build_tree(1, 1, n);
seg2.build_tree(1, 1, n);

for(int i = 1; i <= n; i++) {
int len;
len = odd_palindrome(i);
seg1.cover(1, 1, n, i, i + len - 1, -i + 1);
seg2.cover(1, 1, n, n - i + 1, n - i + len, -n + i);
}
for(int i = 1; i <= n; i++) pre[i] = i + seg1.query(1, 1, n, i);
for(int i = 1; i <= n; i++) suf[i] = i + seg2.query(1, 1, n, i);
reverse(suf + 1, suf + n + 1);
for(int i = 2; i <= n - 1; i++)
if(s[i] == '#') ans = max(ans, pre[i - 1] + suf[i + 1]);
printf("%d\n", ans);
return 0;
}
• star
首页