P4036 题解

AC_love · 2024-05-27 07:45:22 · 题解

大家好，我很喜欢暴力数据结构，于是我打算用分块来做这道题。

此题有插入操作，因此普通的静态分块无法解决问题，考虑块状链表。

首先众所周知，块状链表可以轻而易举做到此题其他题解中平衡树做的事情：维护一个区间 [l, r] 的哈希值。但这个操作用块状链表来做复杂度为 O(\sqrt n)，对比 O(\log n) 的平衡树并不占优势。

同时我们知道，分块和二分是天生八字不合的算法，此题中如果对分块算法使用二分，单次询问复杂度将会达到 O(\sqrt n \log n)。由于本题询问操作很少，所以貌似可以通过（连 O(n) 的暴力都能通过，这个没理由过不去），但看起来真的很劣。

所以对于块状链表做法，我们不考虑使用二分回答询问，而是直接暴力跳块。

详细点说，做法如下：

预处理：对于每个块，维护每个前缀的 hash 值。

修改：修改一个字符，然后修改所有包括这个字符的前缀的 hash 值。

插入：插入一个字符，把它后面的字符整体往后挪一位，然后再修改所有包括这个插入字符的前缀的 hash 值。

询问：从两个点开始，每次一步跳 \sqrt n 格，如果跳完之后还相等，那么继续跳。如果跳完之后不相等，直接暴力跳 \sqrt n 步找到第一个不相等的位置即可。

考虑一下复杂度。

当块的长度和每个块内元素都为 \sqrt n 级别时，修改和插入操作最多改一整个块，复杂度 O(\sqrt n)；询问操作中，暴力跳块最多只会跳过 \sqrt n 个块，复杂度 O(\sqrt n)。当发现不同之处，开始暴力跳时，最多跳 \sqrt{n} 个字符就能找到差异，复杂度还是 O(\sqrt n)。

每个操作都是 O(\sqrt n) 的复杂度，而预处理复杂度为 O(n \sqrt n)。故总复杂度为 O((n + m) \sqrt n)。

本题中 n, m 近乎同阶，复杂度可视为 O(n \sqrt n)，相比 O(n \log^2 n) 的平衡树未必不占优势（KH：支持正义根号！）。

评测记录

本人代码总用时 1.70s，比大部分平衡树跑的都快，起码如果让我自己写一个平衡树的话肯定没有我的块状链表跑得快。

~~我踩过的坑点~~ 一些需要注意的点：

本题中插入操作是“在第 x 个字符后面插入”，而一些写法的插入操作是“在第 x 个字符前面插入”。如果你采用了这样的写法，记得读入插入操作后将 x 增加 1。
在询问跳块时，可能会发生跳到字符串外面的情况，导致溢出。特判很麻烦，我的解决办法是在读入的字符串后面加入足够多的特殊字符。
需要注意，如果你也加入了特殊字符，请务必特判 Q x x 这种情况，否则这两个东西会一直跳下去，直到跳到字符串外面。

同时众所周知的，块状链表题目不给代码约等于耍流氓（AClove：口嗨谁不会啊），因此我们在下面对于每种操作的代码进行详解：

一个块内应该维护的信息：

struct block
{
    char c[S * 5 + 100];
    // 记录块内的所有字符
    int pre[S * 5 + 100];
    // pre 数组维护每个前缀 hash
    int sz;
    // sz 维护这个块的大小
    int lef, rig;
    // lef, rig 记录当前块的左块和右块编号
    int head;
    // head 记录这个块前面有多少个字符
    int hash(int l, int r) { return ((pre[r] - pre[l - 1] * p[r - l + 1] % mod) + mod) % mod; }
    // 快速求一个区间的 hash 值
    void push_back(char val) { c[++ sz] = val; pre[sz] = (pre[sz - 1] * base + val - 'a' + 1) % mod; }
    // 插入一个新字符
};
block c[S * 2 + 10];

修改一个位置的字符：

void change(int pos, char val)
{
    int ps = bl[pos], w = pos - c[ps].head;
    // ps 是 val 处于哪个块，w 是 val 在块中的位置
    c[ps].c[w] = val;
    // 修改这个位置的字符
    for(int i = w; i <= c[ps].sz; i = i + 1)
        c[ps].pre[i] = (c[ps].pre[i - 1] * base + c[ps].c[i] - 'a' + 1) % mod;
        // 修改所有包含这个位置的前缀哈希
}

向一个位置插入元素：

需要注意的是，只有当每个块的大小都接近 \sqrt n 时块状链表的复杂度才能保证。如果你一直往一个块里插入元素，会导致这个块变得很大，复杂度可能退化成 O(n^2)。因此要在块比较大的时候把块拆开。

void split(int id)
// 把 id 这个块拆了
{
    c[++ blocks].lef = id;
    c[blocks].rig = c[id].rig;
    c[c[id].rig].lef = blocks;
    c[id].rig = blocks;
    // 开一个新块

    for(int i = S + 1; i <= c[id].sz; i = i + 1)
    {
        c[blocks].push_back(c[id].c[i]);
        // 把插入新字符
        c[id].c[i] = c[id].pre[i] = 0;
        // 清除旧块中的信息
    }
    c[id].sz = S;
    // 重置旧块的大小
    c[blocks].head = c[id].head + S;
    // 计算新块前面有多少个字符
    for(int i = c[blocks].head + 1; i <= c[blocks].head + c[blocks].sz; i = i + 1)
        bl[i] = blocks;
        // 更新 bl 数组
}

void insert(int pos, char val)
{
    int ps = bl[pos], w = pos - c[ps].head;
    // ps 是 val 处于哪个块，w 是 val 在块中的位置
    for(int i = c[ps].sz + 1; i >= w + 1; i = i - 1)
        c[ps].c[i] = c[ps].c[i - 1];
        // 把 w 后面的字符整体右移一位
    c[ps].c[w] = val;
    // 修改这个位置的字符
    c[ps].sz ++;
    // 更新块长
    for(int i = w; i <= c[ps].sz; i = i + 1)
        c[ps].pre[i] = (c[ps].pre[i - 1] * base + c[ps].c[i] - 'a' + 1) % mod;
        // 修改所有包含这个位置的前缀哈希
    for(int i = ps; i; i = c[i].rig)
    {
        if(i != ps)
            c[i].head ++;
        // 把后面的所有块的前面的字符数 +1
        bl[c[i].head + 1] = i;
        bl[c[i].head + c[i].sz] = i;
        // 更新 bl 数组
    }
    if(c[ps].sz >= S * 2)
        split(ps);
        // 如果当前块长度太长，就把它拆了
}

询问：

int jump(int pos, int k)
// 计算 pos 跳 k 步后的哈希值
{
    int ps = bl[pos], w = pos - c[ps].head;
    // ps 是 val 处于哪个块，w 是 val 在块中的位置
    int suf = c[ps].sz - w + 1;
    // 计算 w 后面有几个字符
    if(suf >= k)
        return c[ps].hash(w, w + k - 1);
        // 如果还在块内，那么直接快速计算
    return (c[ps].hash(w, w + suf - 1) * p[k - suf] % mod + jump(pos + suf, k - suf)) % mod;
    // 否则先把当前块跳完，然后去跳下一个块
}

bool cmp(int l1, int l2)
// 比较两个位置的字符是否相等
{
    int ps1 = bl[l1], w1 = l1 - c[ps1].head;
    int ps2 = bl[l2], w2 = l2 - c[ps2].head;
    return c[ps1].c[w1] == c[ps2].c[w2];
}

int query(int l1, int l2)
{
    int res = 0;
    while(jump(l1, S) == jump(l2, S))
    {
        res += S;
        l1 += S;
        l2 += S;
    }
    while(cmp(l1, l2))
    {
        l1 ++;
        l2 ++;
        res ++;
    }
    return res;
}

初始化：

void build()
{
    for(int i = 1; i <= len; i = i + 1)
    {
        bl[i] = (i - 1) / S + 1;
        c[bl[i]].push_back(s[i]);
        // 向块内插入一个字符
        blocks = bl[i];
        // 更新块数
    }
    for(int i = 1; i <= blocks; i = i + 1)
        c[i].lef = i - 1,
        c[i].rig = i + 1,
        c[i].head = (i - 1) * S;
        // 维护每个块的左右块
    c[blocks].rig = 0;
    // 最右边的块右边没有块
}

以上就是本题的所有核心操作，代码的其他部分没啥意义，就不放了。