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

CPP

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

CF2118F Shifts and Swaps

文章操作

相关推荐

评论

CF2118F Shifts and Swaps