Solution Set - 训练计划链表

liuzimingc / 2024-02-01 / 原文

咕掉了两道不可做题（指黑色）。

梦幻布丁

放在链表的题单里，和链表有什么关系呢？？？

因为都是在对颜色整体进行操作，我们可以根据颜色拉出来对应的链表。

那么每次合并就相当于把一个链表接到另一个链表上去，暴力修改，那么是 $O(n)$ 的，但是要怎么维护答案呢？

首先可以处理出不做任何操作时的答案 $ans = 1 + \sum_{i = 2} ^ n [a_i \not= a_{i - 1}]$。那么假设每次将颜色 $x$ 更改为 $y$，只会引起 $c_{i - 1}$ 或 $c_{i + 1}$ 统计的变化（就是上面那个式子），变化量就是 $\sum\limits_{c_i = x} [c_{i - 1} = y] + [c_{i + 1} = y]$，减去就好了。

但是你看，这一次 $O(n)$ 不直接飞起？引入一个非常 NB 的东西：启发式合并。就是每次小的接到大的上面去，时间复杂度不会证，但类似并查集的启发式合并，均摊下来是 $O(\log n)$ 的。这样就完了。

以及说维护链表类似于链式前向星那样记录的，具体可以看代码。

namespace liuzimingc {
const int N = 1e6 + 5;

int n, m, a[N], ed[N], nxt[N], head[N], siz[N], ans, fa[N];

void merge(int x, int y) {
    for (int i = head[x]; i; i = nxt[i]) ans -= (a[i - 1] == y) + (a[i + 1] == y);
    for (int i = head[x]; i; i = nxt[i]) a[i] = y;
    nxt[ed[x]] = head[y];
    head[y] = head[x];
    siz[y] += siz[x];
    head[x] = ed[x] = siz[x] = 0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        fa[a[i]] = a[i];
        if (!siz[a[i]]) ed[a[i]] = i; // 链表的最末端 
        siz[a[i]]++;
        nxt[i] = head[a[i]];
        head[a[i]] = i;
        ans += a[i] != a[i - 1];
    }
    while (m--) {
        int op, x, y;
        cin >> op;
        if (op == 1) {
            cin >> x >> y;
            if (x == y) continue;
            if (siz[fa[x]] > siz[fa[y]]) swap(fa[x], fa[y]);
            if (!siz[fa[x]]) continue;
            merge(fa[x], fa[y]);
        }
        else cout << ans << endl;
    }
	return 0;
}
} // namespace liuzimingc