题目描述

难度分:$1800$

输入$T(\leq 10^5)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$，$m$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，表示一个$n$个点的图，一开始没有边。节点编号从$1$到$n$。

然后输入$m(1 \leq m \leq 2 \times 10^5)$和$m$个操作。

每个操作输入$a$、$d$、$k(1 \leq a \leq a+k \times d \leq n$， $1 \leq d \leq 10$，$0 \leq k \leq n)$，表示一个等差数列$a,a+d,a+2d,…,a+k \times d$。把等差数列中的所有点两两连边。

输出$m$个操作之后，这个图有多少个连通块。

输入样例

3
10 2
1 2 4
2 2 4
100 1
19 2 4
100 3
1 2 5
7 2 6
17 2 31

输出样例

2
96
61

算法

离线+并查集+双指针

我们按照$d$和$rd=a \% d$，对所有操作进行分类。构建一个映射$seg$，$seg[d][rd]$表示被分在$(d,rd)$这个组数的左右端点二元组$(left,right)$，其中$left=a$，$right=a+k \times d$。然后遍历$d$和$rd$，对每个组内的区间$v$按照左右端点二次排序。对于同一类操作，如果某两个操作的点有交集，那么这两个操作等价于他们合并之后的操作，因为这两个操作中的任意一个点都可以先走到交集中的某个点，再走到另一个点。于是这两个操作并集中的所有点最后都会在同一个连通分量中。

所以，对于每一类操作，可以排序后使用双指针进行集合求并，得到若干个极大的操作，然后再使用并查集进行暴力连边。这样可以保证每个点最多只会被暴力操作$10$次。

复杂度分析

时间复杂度

集合合并的时间复杂度仅和边数有关，时间复杂度为$O(mlogm)$。每个节点暴力连边的时间复杂度为$O(n \times max_{i \in [1,m]}d_i)$，$max_{i \in [1,m]}d_i=10$，因此可以看成是$O(n)$。整个算法的时间复杂度为$O(mlogm+n)$。

空间复杂度

并查集的空间消耗为$O(n)$；$seg$中会存$O(m)$条边；因此，整个算法的额外空间复杂度为$O(n+m)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
int T, n, m, a, d, k;

struct DSU {
    vector<int> fa, sz;
    DSU(int n): fa(n + 1), sz(n + 1, 1) {
        iota(fa.begin(), fa.end(), 0);
    }
    inline int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }

    inline bool same(int x, int y) {
        return find(x) == find(y);
    }

    inline bool merge(int x, int y) {
        if(same(x, y)) return false;
        int fx = find(x), fy = find(y);
        if(sz[fx] < sz[fy]) swap(fx, fy);
        fa[fy] = fx, sz[fx] += sz[fy], sz[fy] = 0;
        return true;
    }
};

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        vector<PII> seg[11][11];
        for(int i = 1; i <= m; i++) {
            scanf("%d%d%d", &a, &d, &k);
            seg[d][a % d].push_back({a, a + k*d});
        }
        DSU dsu(n);
        int ans = n;
        for(int d = 1; d <= 10; d++) {
            for(int rd = 0; rd < d; rd++) {
                auto& v = seg[d][rd];
                int sz = v.size();
                sort(v.begin(), v.end());
                for(int l = 0, r = 0; l < sz; l = r) {
                    int L = v[l].first, R = v[l].second;
                    while(r < sz && v[r].first <= R) {
                        R = max(R, v[r].second);
                        r++;
                    }
                    for(int j = L; j < R; j += d) {
                        ans -= dsu.merge(j, j + d);
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}