P5397 & P5962 题解

省流：啊宝宝你是一个 P4117 + P4119 + P5611（所以这题题号为什么不是 P13847）。

模拟赛看到了这玩意，想了依托做法，随便写了个常数巨大的代码然后跑的飞慢，最后喜提暴力分。

不妨先假设 同阶，然后扔掉修改。

来想想暴力咋做。

首先你可以从前往后扫描，维护最后一个 出现的位置和 出现的位置。每次遇到 或者 就更新一下答案，然后更新位置。这样就是 做法。以防你不知道我的巨大常数代码最后分数和这个一样。

然后你考虑上点手段优化一下这个过程。

我们还有另外一个做法。就是你考虑预处理出来每个值 的答案 ，然后查询的时候直接查表。不过这样复杂度仍然是平方，没啥用。

但是我们现在有两个看上去不同的做法，我们能不能取长补短？

此时我们可以仿照 P5611 进行一个等价类分治的思想。把序列每 个元素分一个块。这样每个块内部的 对数只有 个。我们可以很轻松的预处理。

此时我们还需要处理 在不同块的情况。对于每个块内部出现的元素 ，维护其在块中最先出现的位置和最后出现的位置 即可。此时再使用方法 ，维护 最后出现的位置 ，每次遇到一个块，先用 最先出现的位置更新答案，然后用 块内最后出现的位置更新两个 。

块内预处理的复杂度是 。遍历每个块查询的复杂度是 。然后你发现应该取 达到一个单根号的复杂度。

好的，此时考虑修改怎么做。

如果没出现直接跳过。 如果没出现那么你对所有 做一个重命名即可。

下面讨论 都出现的情况。对于第一次和最后一次的出现位置，我们令 即可。

考虑 。我们发现，由于修改之后所有 变成了 ，原来的 也有可能成为 之间的最短距离了，因此你对所有块内出现的 ，令 。 同理。

分析一下复杂度。发现是每个块做一次都是 的。单词修改做 个块，不是爆了？

但是注意这个修改十分特殊，是把所有的 改成 ，相当于是之前的 和 合并成了一个大集合。

因此，修改到最后，序列里不同的数的个数会越来越少。因此你考虑对这个东西进行势能分析。

首先，只有当 都在块内部出现的时候，才有合并的必要。否则做重命名是 的。

而合并之后，块内部不同元素个数会减少 。显然此操作只会至少有 种不同的元素时才会进行。因此一个块最多进行 次这样的操作。

而每个块都是如此，总共是 次，每次 ，复杂度 。

然后你发现你应该取 达到一个单根号的复杂度。

然后你发现你还可以把这个题目顺手加强一下变成区间修改和区间查询。

区间查询的方式大致和上面的过程一样，左右两侧的散块可以暴力。

区间修改对于中间完整的块仍然是上面的修改方法。两侧的散块我们需要重构。不过我们并不用重构整个 ，我们发现只有 这些值会发生改变。我们从前往后扫描一遍，维护最后一个 和最后一个 ，遇到一个数 就用最后一个 和 来更新 。然后从后往前扫一遍做同样的事情。

至于分配新的编号，直接扫一遍找到空闲编号分配即可。

注意到这样两边块的不同元素个数至多会增加 ，因此我们的势能分析仍然成立，总操作次数 。

取块长根号就能得到一个单根号做法。

代码略，因为我还没卡进 500ms。

---

UPD ：卡过去了，下面是代码。

▶

INFO

#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <unordered_map>
#include <vector>

using ushort = unsigned short;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using u8 = uint8_t;

#if 0
#include <fstream>

std::ifstream fin("ikaros.in");
std::ofstream fout("ikaros.out");
#else
#include <iostream>

std::istream &fin = std::cin;
std::ostream &fout = std::cout;
#endif

namespace solve {
const uint V = 1e5 + 5;
const uint B = 256;
const uint CB = 391;

const u8 npos = -1;

std::array<std::array<std::array<u8, 2>, CB>, V> pos;
std::array<std::bitset<512>, V> has_val;

struct block {
    // 最先和最后的 pos。

    // 块内部的 index。

    std::array<std::array<u8, B>, B> min_dis;
    uint bindex;

    /**
     * 从 x 合并到 y。
     */

    void merge(uint x, uint y) {
        pos[y][bindex][1] = std::max(pos[y][bindex][1], pos[x][bindex][1]);

        uint u = pos[x][bindex][0], v = pos[y][bindex][0];

        if (u < v) {
            std::swap(u, v);
            pos[y][bindex][0] = pos[x][bindex][0];
        }

        for (size_t i = 0; i < B; i++) {
            if (min_dis[u][i] < min_dis[v][i]) {
                min_dis[v][i] = min_dis[u][i];
                min_dis[i][v] = min_dis[v][i];
            }
            /**
             * 让我们直接相信不会继续访问 u 了。
             *
             * 相信对了。
             *
             * 后面不会访问，所以没必要清空。
             */
        }
    }

    uint query(uint x, uint y) const {
        uint u = pos[x][bindex][0], v = pos[y][bindex][0];
        return min_dis[u][v];
    }

    void build(const std::vector<uint> &x) {
        for (auto &&i : min_dis) {
            i.fill(npos);
        }

        for (uint i = 0; i < x.size(); i++) {
            if (!has_val[x[i]][bindex]) {
                has_val[x[i]][bindex] = true;
                pos[x[i]][bindex][0] = i;
                pos[x[i]][bindex][1] = i;
                min_dis[i][i] = 0;
            }
            const auto ind = x[i];
            pos[ind][bindex][1] = i;
        }

        for (uint i = 0; i < x.size(); i++) {
            for (uint j = 0; j < i; j++) {
                uint u = pos[x[i]][bindex][0], v = pos[x[j]][bindex][0];
                min_dis[u][v] = std::min<u8>(min_dis[u][v], i - j);
                min_dis[v][u] = min_dis[u][v];
            }
        }
        return;
    }

    void rename(uint x, uint y) { pos[y][bindex] = pos[x][bindex]; }
};

void solve() {
    uint n, q;

    fin >> n >> q;

    uint cnt = (n + B - 1) / B;

    std::vector<block> blk(cnt);

    std::vector<uint> vec(n);
    for (size_t i = 0; i < n; i++) {
        fin >> vec[i];
    }

    for (uint i = 0; i < blk.size(); i++) {
        uint ed = std::min(n, (i + 1) * B);
        blk[i].bindex = i;
        blk[i].build(std::vector<uint>(vec.begin() + i * B, vec.begin() + ed));
    }

    uint last = 0;

    auto hval = [](uint x, uint i) { return has_val[x][i]; };

    while (q--) {
        uint op;
        uint x, y;
        fin >> op >> x >> y;

        x ^= last;
        y ^= last;

        --op;
        if (!op) {
            uint u = x, v = y;
            if (x == y) {
                continue;
            }

            /**
             * 都有的情况。
             *
             * 这就需要合并了。
             */

            auto mg = has_val[u] & has_val[v];
            auto single = has_val[u] ^ mg;

            for (size_t i = mg._Find_first(); i < cnt; i = mg._Find_next(i)) {
                blk[i].merge(u, v);
            }

            for (size_t i = single._Find_first(); i < cnt;
                 i = single._Find_next(i)) {
                blk[i].rename(u, v);
            }

            has_val[v] |= has_val[u];
            has_val[u].reset();
        }
        else {
            const uint u = x, v = y;

            uint ans = 0x3f3f3f3f;

            const uint np = n + 1;

            /**
             * 神秘技巧。
             *
             * 因为 last 全都是减法，而减掉 n + 1 可以让它溢出成一个很大的数。
             */

            uint lastu = np, lastv = np;

            auto appera = has_val[u] | has_val[v];

            for (uint i = appera._Find_first(); i < cnt && ans > 1;
                 i = appera._Find_next(i)) {
                const std::array<u8, 2> &vu = pos[u][i], vv = pos[v][i];

                if (hval(u, i) && hval(v, i)) {
                    ans = std::min(blk[i].query(u, v), ans);
                }

                if (hval(u, i)) {
                    ans = std::min(ans, vu[0] + (i * B) - lastv);
                }

                if (hval(v, i)) {
                    ans = std::min(ans, vv[0] + (i * B) - lastu);
                }

                if (hval(u, i)) {
                    lastu = vu[1] + i * B;
                }

                if (hval(v, i)) {
                    lastv = vv[1] + i * B;
                }
            }

            if (ans == 0x3f3f3f3f) {
                fout << "Ikaros\n";
                last = 0;
            }
            else {
                last = ans;
                fout << ans << "\n";
            }
        }
    }
    return;
}
} // namespace solve

UPD ：怎么区间修改版本已经有了。题号 P5692。