自动搬运

查看原文

来自洛谷，原作者为

	Clever_Jimmy AFO

搬运于2025-08-24 22:20:23，当前版本为作者最后更新于2020-04-18 13:29:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

update: 已更正一处错误，不应称之为“虚树”，而是“优化建图”。

我简述了一下题意，若不想看 冗长 的题面的，可以看一下。

题意简述：

给定一个字符串 $S_0$，有 $q$ 组询问，每次问由 $S_0$ 变为 $S_0[l \ldots r]$ 所需要经过的最小花费。

操作 1：$S \gets T$，其中 $T$ 为 $S$ 的最长回文后缀，此操作花费为 $A$；

操作 2：$S \gets T$，其中 $S$ 为 $T$ 的最长回文后缀，且 $T$ 为 $S_0$ 的子串，此操作花费为 $B$；

操作 3：对于非空的 $S \gets T$，其中 $T$ 为 $S$ 删除长度 不大于 $k$ 的前缀与后缀得到的，此操作花费为 $C$；

操作 4：对于非空的 $S \gets T$，其中 $T$ 为 $S_1+S+\overleftarrow{S_1}$，且 $T$ 为 $S_0$ 的子串，此操作花费为 $D$；

操作 5：对于非空的 $S \gets T$，其中 $T$ 为 $c + S$，$c$ 为任意字符，且 使用此操作后，在以后的操作中，不允许再使用其他操作，此操作花费为 $E$；

对于 $100\%$ 的数据，保证 $1 \le \left|S_0\right|, q \le 10^5$，$1 \le \left|\Sigma\right| \le 52$。

解题思路：

操作 1

直接连 $(i, fail_i)$，边权为 $A$ 的边即可。

操作 2

直接连 $(fail_i, i)$，边权为 $B$ 的边即可。

操作 3

预处理出 $i$ 的父亲 $fa_i$，然后连 $k$ 条 $(i, fa_i)$，边权为 $C$ 的边。

操作 4

这个操作，本质上是从 $i$ 以 $D$ 的代价转移到 $i$ 子树中的任意一个结点。

但是，考虑到 $i$ 的子树可能会非常大，依次连接于边数或是时间复杂度上均不合理。

考虑优化建图的思想，对每个点建立一个对应的虚点，而虚点 只能往儿子的方向 转移（花费为 $0$）。

那么，连一条 $(i, i')$，边权为 $D$ 的边，以及 $(i', i)$，边权为 $0$ 的边即可。

操作 5

操作 5 是独立于上述四个操作的，因为进行完一次操作 5 后 不能再使用 上述四个操作了。

这个倍增一下 level ancestor，结合 dp 转移即可。

设 $dis_i$ 表示 Dijkstra 求出来的最短路的距离，

设 $f(i)$ 表示使用五种操作到达 $i$ 的最少花费，则 $f(i) = \min\{dis_i, f(fail_i) + E\cdot(len_i - len_{fail_i})\}$

时间复杂度分析

记 $\left|S\right| = n$。

显然边的数量是线性的，不难得出最后的时间复杂度为 $O((n + q)\log(n))$。

可以使用配对堆优化 Dijkstra。

参考代码：

Dijkstra 我就不贴了。

#include <bits/stdc++.h>
#define LL long long

const LL inf = 0x3f3f3f3f3f3f3f3fLL;
const int N = 1e6 + 5;
const int M = 2e6 + 5;

int n, m, k, ta, tb, tc, td, te, q, flag = 1;
int cnt, first[N], pos[N];
LL dis[N], f[N];
int lg2, anc[N][40 + 5];
char str[N];

struct EERTREE {
    static const int MS = N;
    static const int C = 50 + 5;

    int n, cntNode, last, s[MS], len[MS], fail[MS], par[MS], ch[MS][C], lst[MS];

    int make(int l) {
        for(int i = 0; i < C; ++i) ch[cntNode][i] = 0;
        len[cntNode] = l;
        return cntNode++;
    }
    int GetFail(int x) {
        while(s[n] != s[n - len[x] - 1]) x = fail[x];
        return x;
    }
    void extend(int x) {
        s[++n] = x;
        int fa = GetFail(last);
        if(!ch[fa][x]) {
            int now = make(len[fa] + 2);
            fail[now] = ch[ GetFail(fail[fa]) ][x];
            ch[fa][x] = now;
        }
        last = ch[fa][x];
        par[last] = fa, lst[n] = last;
    }
    void init() {
        n = cntNode = last = 0;
        make(0), make(-1);
        fail[0] = 1, fail[1] = 0;
        s[0] = -1;
    }
    EERTREE() { init(); }
} t;

int I(char ch) {
    if('a' <= ch && ch <= 'z')
        return ch - 'a' + 1;
    else
        return 26 + ch - 'A' + 1;
}

int G(int x) {
    return x + t.cntNode - 1;
}

void Build_Graph() {
    for(int i = 2; i <= t.cntNode - 1; ++i) {
        if(t.fail[i] > 1) Add_Edge(i, t.fail[i], ta), Add_Edge(t.fail[i], i, tb);
        else Add_Edge(i, 1, ta), Add_Edge(1, i, tb);
        for(int j = 1, fa = t.par[i]; j <= k && fa > 1; ++j, fa = t.par[fa])
            Add_Edge(i, fa, tc);
        Add_Edge(i, G(i), td);
        Add_Edge(G(i), i, 0);
        for(int j = 0; j < t.C; ++j)
            if(t.ch[i][j])
                Add_Edge( G(i), G(t.ch[i][j]), 0 );
    }
    for( ; 1LL << lg2 < m; ++lg2);
    for(int i = 2; i <= t.cntNode - 1; ++i) anc[i][0] = std::max(t.fail[i], 1);
    for(int j = 1; j <= lg2; ++j)
        for(int i = 2; i <= t.cntNode - 1; ++i)
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
}

int Find(int x, int len) {
    if(t.len[x] <= len) return x;
    for(int j = lg2; j >= 0; --j)
        if(anc[x][j] > 1 && t.len[anc[x][j]] > len)
            x = anc[x][j];
    return anc[x][0];
}

void solve(int l, int r) {
    if(l == 1 && r == m) {
        puts("0");
        return;
    }
    int p = Find(t.lst[r], r - l + 1);
    printf("%lld\n", f[p] + 1LL * (r - l + 1 - t.len[p]) * te + (!flag) * ta);
}

int main() {
    scanf("%s", str + 1), m = strlen(str + 1);
    memset(first, -1, sizeof(first));
    scanf("%d %d %d %d %d %d %d", &k, &ta, &tb, &tc, &td, &te, &q);

    for(int i = 1; i <= m; ++i) t.extend( I(str[i]) );
    Build_Graph();
    Dijkstra(t.last);

    for(int i = 1; i <= m; ++i) flag &= (str[i] == str[m - i + 1]);

    f[0] = inf, f[1] = dis[1];
    for(int i = 2; i <= t.cntNode - 1; ++i)
        f[i] = std::min(dis[i], f[t.fail[i]] + 1LL * te * (t.len[i] - t.len[t.fail[i]]));

    while(q--) {
        int l, r;
        scanf("%d %d", &l, &r);
        solve(l, r);
    }
    return 0;
}