题解 P6396 【要有光】

Clever_Jimmy · 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;
}