BZOJ4932 基因

基因

给定一个长度为 \(n\) 的字符串 \(s\)，有 \(q\) 组询问，每个询问给定 \(l,r\)，询问 \(s[l..r]\) 中有多少本质不同的回文子串。

强制在线。\(n\leq 10^5，q ≤ 2n\)。

题解

翁文涛《回文树及其应用》。

“维护每个关键点到每个右端点的回文树”指的是维护 \((i,i\sim n)\) 的回文树。

往前端添加字符，\(fail\) 和 \(quick\) 都同后端一样。

回文树比较好的性质是加入一个之后节点数最多变化1，所以不用清空。

往前端加入字符的时候需要判断新增的节点是不是之前就出现过了的，这个可以对每个块维护每个节点第一次时间（未出现为 inf）。

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

const int N = 101010;
const int M = 350;

inline char get(void) {
    static char buf[100000], *S = buf, *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf, 1, 100000, stdin);
        if (S == T) return EOF;
    }
    return *S++;
}
template<typename T>
inline void read(T &x) {
    static char c; x = 0; int sgn = 0;
    for (c = get(); c < '0' || c > '9'; c = get()) if (c == '-') sgn = 1;
    for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
    if (sgn) x = -x;
}
inline void read(char *s) {
    static char c; int len = 0;
    for (c = get(); c < 'a' || c > 'z'; c = get());
    for (; c >= 'a' && c <= 'z'; c = get()) s[len++] = c;
    s[len] = 0;
}

char s[N];
int last_back, last_front, total;
int fail[N], len[N], ri[N];
int ch[N][30], quick[N][30];
int block_front[M][N], ans[M][N], block_time[M][N];
int visit[N];
int type, lastans, clocks;
int n, q, l, r, B;
int belong[N];

inline void ExtendFront(int pos, int r) {
    int p = last_front, key = s[pos];
    if (s[pos + len[p] + 1] != key || pos + len[p] + 1 > r) p = quick[p][key];
    if (!ch[p][key]) {
        int np = ++total, q = fail[p];
        len[np] = len[p] + 2;
        if (s[pos + len[q] + 1] == key) fail[np] = ch[q][key];
        else fail[np] = ch[quick[q][key]][key];
        memcpy(quick[np], quick[fail[np]], sizeof quick[np]);
        quick[np][s[pos + len[fail[np]]]] = fail[np];
        ch[p][key] = np;
    }
    last_front = ch[p][key];
    if (len[last_front] == r - pos + 1) last_back = last_front;
}
inline void ExtendBack(int l, int pos) {
    int p = last_back, key = s[pos];
    if (s[pos - len[p] - 1] != key || pos - len[p] - 1 < l) p = quick[p][key];
    if (!ch[p][key]) {
        int np = ++total, q = fail[p];
        len[np] = len[p] + 2;
        if (s[pos - len[q] - 1] == key) fail[np] = ch[q][key];
        else fail[np] = ch[quick[q][key]][key];
        memcpy(quick[np], quick[fail[np]], sizeof quick[np]);
        quick[np][s[pos - len[fail[np]]]] = fail[np];
        ch[p][key] = np;
    }
    last_back = ch[p][key];
    if (len[last_back] == pos - l + 1) last_front = last_back;
}

int main(void) {
    read(type); read(n); read(q);
    read(s + 1); s[0] = -1;
    for (int i = 1; i <= n; i++) s[i] -= 'a';
    B = sqrt(n);
    for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;

    memset(block_time, 0x3f, sizeof block_time);
    fail[0] = fail[1] = 1; len[1] = -1; total = 1;
    for (int i = 0; i < 26; i++) quick[0][i] = quick[1][i] = 1;

    for (int i = 0; i < belong[n]; i++) {
        ++clocks; last_back = last_front = 0;
        int st = i * B + 1;
        for (int j = st; j <= n; j++) {
            ExtendBack(st, j);
            block_front[i][j] = last_front; ans[i][j] = ans[i][j - 1];
            if (visit[last_back] != clocks) {
                ++ans[i][j]; visit[last_back] = clocks;
                block_time[i][last_back] = j;
            }
        }
    }

    while (q--) {
        read(l); read(r); ++clocks;
        l ^= type * lastans;
        r ^= type * lastans;
        if (l > r) swap(l, r);
        if (belong[l] == belong[r]) {
            last_back = last_front = 0; lastans = 0;
            for (int i = r; i >= l; i--) {
                ExtendFront(i, r);
                if (visit[last_front] != clocks) {
                    ++lastans; visit[last_front] = clocks;
                }
            }
        } else {
            lastans = ans[belong[l]][r];
            last_front = block_front[belong[l]][r];
            for (int i = belong[l] * B; i >= l; i--) {
                ExtendFront(i, r);
                if (visit[last_front] != clocks) {
                    visit[last_front] = clocks;
                    if (block_time[belong[l]][last_front] > r) ++lastans;
                }
            }
        }
        printf("%d\n", lastans);
    }
    return 0;
}