BZOJ 3790 神奇項鍊 Manacher 樹狀數組

幾個月沒寫manacher忘幹淨了。。。

将一些回文串直接連接配接或前、字尾重複部分完全重疊，産生了新的字元串，問該字元串的連接配接次數。

如abacada

考慮求出所有極長回文串。

即a[1..1,3..3,5..5,7..7],b[2..2,6..6],c[4..4],aba[1..3],aca[3..5],ada[5..7]

發現這些回文串按照其位置放置将區間完整覆寫的方案即我們所求。

也就是說，從一堆線段中，挑選一些，使這些線段完整地覆寫區間[1..7]

如果按右端點排序，那麼對于每個線段i，覆寫到r[i]的可行方案，是之前存在一個方案，覆寫到l[i]-1~r[i]間，是以表示方案為其覆寫到的右端點，每次查詢l[i]-1~r[i]間的方案的最小使用線段樹，也就是單點修改區間查詢，樹狀數組即可。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define FOR(i,j,k) for(i=j;i<=k;++i)
const int inf = , N = ;
int c[N], n, k, p[N]; char s[N], a[ * N];
int query(int i) {
    if (!i) return ;
    int s = inf;
    for (; i <= n; i += i & -i) s = min(s, c[i]);
    return s;
}

void update(int i, int x) {
    for (; i; i -= i & -i) c[i] = min(c[i], x);
}

struct Data { int a, b; } d[N];
bool operator< (const Data &a, const Data &b) { return a.b < b.b; }

void manacher() {
    int mx = , id, m =  * n + , i, l, r;
    for (i = ; i <= n; ++i) {
        a[i * ] = s[i];
        a[i *  + ] = '#';
    }
    a[] = '&'; a[m + ] = '^'; a[] = '#';
    for (i = ; i <= m; ++i) {
        if (mx > i) p[i] = min(mx - i, p[ * id - i]);
        else p[i] = ;
        while (a[i - p[i]] == a[i + p[i]]) ++p[i];
        if (i + p[i] > mx) mx = i + p[i], id = i;
        l = (i - p[i]) /  + ; r = (i + p[i]) /  - ;
        if (l <= r) d[++k] = (Data) { l, r };
    }
}



int main() {
    int ans, i, x;
    while (scanf("%s", s + ) != EOF) {
        n = strlen(s + ); ans = inf; k = ;
        FOR(i,,n) c[i] = inf;
        manacher();
        sort(d + , d + k + );
        FOR(i,,k) {
            x = query(d[i].a - ) + ;
            update(d[i].b, x);
            if (d[i].b == n) ans = min(ans, x);
        }
        printf("%d\n", ans - );
    }
    return ;
}
           

3790: 神奇項鍊

Description

母親節就要到了，小 H 準備送給她一個特殊的項鍊。這個項鍊可以看作一個用小寫字

母組成的字元串，每個小寫字母表示一種顔色。為了制作這個項鍊，小 H 購買了兩個機器。第一個機器可以生成所有形式的回文串，第二個機器可以把兩個回文串連接配接起來，而且第二個機器還有一個特殊的性質：假如一個字元串的字尾和一個字元串的字首是完全相同的，那麼可以将這個重複部分重疊。例如：aba和aca連接配接起來，可以生成串abaaca或 abaca。現在給出目标項鍊的樣式，詢問你需要使用第二個機器多少次才能生成這個特殊的項鍊。

Input

輸入資料有多行，每行一個字元串，表示目标項鍊的樣式。

Output

多行，每行一個答案表示最少需要使用第二個機器的次數。

Sample Input

abcdcba
abacada
abcdef
           

Sample Output

0
2
5
           

HINT

每個測試資料，輸入不超過 5行

每行的字元串長度小于等于 50000