欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷P4555 [国家集训队]最长双回文串(manacher 线段树)

程序员文章站 2022-04-09 18:02:01
题意 "题目链接" Sol 我的做法比较naive。。首先manacher预处理出以每个位置为中心的回文串的长度。然后枚举一个中间位置,现在要考虑的就是能覆盖到i 1的回文串中 中心最靠左的,和能覆盖到i+1中 中心最靠右的,算一下答案取个max。 线段树维护一下区间min, max。标记永久化炒鸡 ......

题意

题目链接

sol

我的做法比较naive。。首先manacher预处理出以每个位置为中心的回文串的长度。然后枚举一个中间位置,现在要考虑的就是能覆盖到i - 1的回文串中 中心最靠左的,和能覆盖到i+1中 中心最靠右的,算一下答案取个max。

线段树维护一下区间min, max。标记永久化炒鸡好写

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10, inf = 1e9 + 10;
char s[maxn];
int len[maxn], n, ans[maxn];
template<typename a, typename b> inline void chmax(a &x, b y) {
    x = x < y ? y : x;
}
template<typename a, typename b> inline void chmin(a &x, b y) {
    x = x < y ? x : y;
}
int root, ls[maxn], rs[maxn], mn[maxn], mx[maxn], tot;
void max(int &k, int l, int r, int ql, int qr, int v) {
    if(!k) k = ++tot, mn[k] = inf;
    if(ql <= l && r <= qr) {chmax(mx[k], v); return ;}
    int mid = l + r >> 1;
    if(ql <= mid) max(ls[k], l, mid, ql, qr, v);
    if(qr  > mid) max(rs[k], mid + 1, r, ql, qr, v);
}
void min(int &k, int l, int r, int ql, int qr, int v) {
    if(!k) k = ++tot, mn[k] = inf;
    if(ql <= l && r <= qr) {chmin(mn[k], v); return ;}
    int mid = l + r >> 1;
    if(ql <= mid) min(ls[k], l, mid, ql, qr, v);
    if(qr  > mid) min(rs[k], mid + 1, r, ql, qr, v);
}
int querymx(int k, int l, int r, int p) {
    int ans = mx[k];
    if(l == r) return ans;
    int mid = l + r >> 1;
    if(p <= mid) chmax(ans, querymx(ls[k], l, mid, p));
    else chmax(ans, querymx(rs[k], mid + 1, r, p));
    return ans;
}
int querymn(int k, int l, int r, int p) {
    int ans = mn[k];
    if(l == r) return ans;
    int mid = l + r >> 1;
    if(p <= mid) chmin(ans, querymn(ls[k], l, mid, p));
    else chmin(ans, querymn(rs[k], mid + 1, r, p));
    return ans;
}
void trans() {
    static char tmp[maxn];
    for(int i = 1; i <= n; i++) {
        tmp[2 * i - 1] = s[i];
        tmp[2 * i] = '#';
    }
    memcpy(s, tmp, sizeof(s));
    n = (n << 1) - 1;
    int mx = 0, id = 0;
    for(int i = 1; i <= n; i++) {
        ans[i] = (mx > i ? min(mx - i, ans[id * 2 - i]) : 1);
        while(s[i - ans[i]] == s[i + ans[i]]) ans[i]++;
        if(i + ans[i] > mx) mx = i + ans[i], id = i;
        max(root, 1, n, i - ans[i] + 1, i, i);
        min(root, 1, n, i, i + ans[i] - 1, i);
    }
}
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    trans();
    int ans = 0;
    for(int i = 2; i <= n; i += 2) {
        chmax(ans, (i - 1 - querymn(root, 1, n, i - 1)) + 1 + (querymx(root, 1, n, i + 1) - i - 1) + 1);
    }
    cout << ans;
    return 0;
}