AcWing 2572. 生成魔咒 题解

题目分析

本题中魔咒串由魔咒字符组成，魔咒字符用数字表示。初始魔咒串为空，通过(n)次操作在串尾添加魔咒字符，每次操作后需计算当前魔咒串的生成魔咒（非空子串）的种类数。

解题思路

本题主要借助后缀数组来求解。通过构造后缀数组及其相关的(height)数组，利用后缀数组的性质计算不同后缀之间的最长公共前缀，进而得出不同非空子串（生成魔咒）的数量。
1. 对输入的魔咒字符进行离散化处理，方便后续构造后缀数组。
2. 使用基数排序和倍增算法构造后缀数组(sa)和(height)数组。
3. 根据后缀数组和(height)数组计算不同阶段的生成魔咒数量。

代码逐段分析

1. 头文件和全局变量定义

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];
int u[N], d[N];
LL ans[N];

• 引入必要的头文件，包括输入输出、字符串操作、算法和哈希表相关的头文件。
• 定义LL为long long的别名。
• 定义常量(N)表示最大的魔咒串长度。
• 变量(n)表示操作次数，(m)用于离散化处理时记录不同魔咒字符的数量。
• s[N]存储魔咒串字符。
• sa[N]、x[N]、y[N]、c[N]、rk[N]、height[N]用于构造和存储后缀数组相关信息。
• u[N]和d[N]用于维护后缀之间的关系，类似双向链表。

• ans[N]用于存储每次操作后生成魔咒的种类数。

• 离散化函数

int get(int x)
{
    static unordered_map<int, int> hash;
    if (hash.count(x) == 0) hash[x] = ++ m;
    return hash[x];
}

• 该函数用于对输入的魔咒字符进行离散化。使用哈希表hash记录每个魔咒字符对应的离散化值。如果字符(x)是第一次出现，为其分配一个新的离散化值（(++m)），并返回该值；否则直接返回已有的离散化值。

• 构造后缀数组函数

void get_sa()
{
    for (int i = 1; i <= n; i ++ ) c[x[i] = s[i]] ++ ;
    for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
    for (int i = n; i; i -- ) sa[c[x[i]] -- ] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for (int i = n - k + 1; i <= n; i ++ ) y[ ++ num] = i;
        for (int i = 1; i <= n; i ++ )
            if (sa[i] > k)
                y[ ++ num] = sa[i] - k;
        for (int i = 1; i <= m; i ++ ) c[i] = 0;
        for (int i = 1; i <= n; i ++ ) c[x[i]] ++ ;
        for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
        for (int i = n; i; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1, num = 1;
        for (int i = 2; i <= n; i ++ )
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        if (num == n) break;
        m = num;
    }
}

• 该函数通过基数排序和倍增算法构造后缀数组(sa)。
• 首先进行第一轮基数排序，统计每个离散化后的字符的出现次数并确定初始排名。

• 然后通过倍增的方式，每一轮根据上一轮的结果重新排序，直到所有后缀的排名都不同。

• 计算Height数组函数

void get_height()
{
    for (int i = 1; i <= n; i ++ ) rk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; i ++ )
    {
        if (rk[i] == 1) continue;
        if (k) k -- ;
        int j = sa[rk[i] - 1];
        while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++ ;
        height[rk[i]] = k;
    }
}

• 该函数用于计算(height)数组，根据后缀数组(sa)先计算出(rk)数组（(sa)的逆数组）。

• 然后从第二个后缀开始，逐步计算每个后缀与前一个后缀的最长公共前缀长度并存储在(height)数组中。

• 主函数

int main()
{
    scanf("%d", &n);
    for (int i = n; i; i -- ) scanf("%d", &s[i]), s[i] = get(s[i]);

    get_sa();
    get_height();

    LL res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        res += n - sa[i] + 1 - height[i];
        u[i] = i - 1, d[i] = i + 1;
    }
    d[0] = 1, u[n + 1] = n;

• 读入操作次数(n)，然后倒序读入每次操作添加的魔咒字符，并进行离散化处理。
• 构造后缀数组和计算(height)数组。
• 初始化结果变量res，遍历后缀数组，计算初始的生成魔咒数量。这里n - sa[i] + 1表示以第(i)个后缀开头的子串数量，减去height[i]是因为要去除与前一个后缀重复的部分。同时初始化u[i]和d[i]构成双向链表结构。

    for (int i = 1; i <= n; i ++ )
    {
        ans[i] = res;
        int k = rk[i], j = d[k];
        res -= n - sa[k] + 1 - height[k];
        res -= n - sa[j] + 1 - height[j];
        height[j] = min(height[j], height[k]);
        res += n - sa[j] + 1 - height[j];
        d[u[k]] = d[k], u[d[k]] = u[k];
    }

    for (int i = n; i; i -- ) printf("%lld\n", ans[i]);

    return 0;
}

• 再次遍历，根据当前添加的魔咒字符，更新生成魔咒的数量。
  • 先记录当前的结果res到ans[i]。
  • 然后从结果中减去当前后缀和其后续后缀原来的贡献值。
  • 更新后续后缀的height值（取较小值），并重新计算其贡献值加入结果。
  • 调整双向链表结构，去除当前后缀。
• 最后倒序输出每次操作后生成魔咒的种类数。

时间复杂度分析

• 离散化处理的时间复杂度为(O(n))。
• 构造后缀数组和计算(height)数组的时间复杂度为(O(n \log n))。
• 计算生成魔咒数量的两个循环，每个循环的时间复杂度为(O(n))，总体时间复杂度为(O(n \log n))。

空间复杂度分析

主要空间消耗在于存储各种数组和哈希表，空间复杂度为(O(n))。