CF2118F Shifts and Swaps

· · 题解

首先注意数据范围保证 1\sim m 均出现。

对于一操作，只需将序列看作环即可处理。对于二操作，本质上就是 |a_i-a_j|\le 1 的数对相对位置不变。

对于 a_i < m 的位置，找到其后（环上）第一个 a_i+1 的位置 j，然后连边 j\to i。这样连出的外向有根树中，子树内的任何值都是不能跨出该子树的。

同时还要注意，对于一个点的所有儿子，它们的值全相等，因此也是不能交换顺序的。即这些树的儿子必须按照一定顺序排列，可以钦定 i 的儿子是从 i 后第一个 a_i-1 的位置开始，环状排列。

如此得到序列的森林。两个序列可相同就是森林循环同构。将每棵树哈希后，使用最小表示法判断两个序列是否循环同构即可。

有根树可以确定性哈希。用一个 map <vector <int>, int> 记录，i 子树的可用一个 vector 表示（先插入 i，再依次插入儿子哈希值）。若该 vector 存在于 map 中，则直接调用；否则赋值新的编号。

时间复杂度 \mathcal O(n\log n)。

AC record

int n, m; map <vector <int>, int> mp;
vector <int> pos[MAXN], g[MAXN];

il auto minimum(vector <int> sec) {
    int k = 0, i = 0, j = 1, n = sec.size();
    while (k < n && i < n && j < n) {
        if (sec[(i + k) % n] == sec[(j + k) % n]) k++;
        else {
            sec[(i + k) % n] > sec[(j + k) % n] ? i = i + k + 1 : j = j + k + 1;
            if (i == j) i++;
            k = 0;
        }
    } i = min(i, j);
    rotate(sec.begin(), sec.begin() + i, sec.end());
    return sec;
}

il void solve() {
    read(n, m); vector <int> a, b; a.resize(n); b.resize(n);
    for (auto &v : a) read(v);
    for (auto &v : b) read(v);
    auto calc = [&](vector <int> a) {
        rep1(i, 1, m) pos[i].clear();
        rep1(i, 0, n - 1) g[i].clear(), pos[a[i]].eb(i);
        rep1(i, 0, n - 1) if (a[i] < m) {
            auto &p = pos[a[i] + 1];
            auto it = upper_bound(begin(p), end(p), i);
            if (it == end(p)) it = begin(p);
            g[*it].eb(i);
        }
        rep1(i, 0, n - 1) {
            auto it = lower_bound(begin(g[i]), end(g[i]), i);
            rotate(begin(g[i]), it, end(g[i]));
        } vector <int> ans;
        auto dfs = [&] (auto self, int x) -> int {
            vector <int> ch; ch.eb(a[x]);
            for (auto v : g[x]) ch.eb(self(self, v));
            if (!mp.count(ch)) mp[ch] = mp.size();
            return mp[ch];
        };
        rep1(i, 0, n - 1) if (a[i] == m) ans.eb(dfs(dfs, i));
        return minimum(ans);
    }; puts(calc(a) == calc(b) ? "YES" : "NO");
}

int main() {
    for (int T = read(); T--; ) solve();
    return 0;
}