题目描述
难度分:1800
输入T(≤105)表示T组数据。所有数据的n之和≤2×105,m之和≤2×105。
每组数据输入n(1≤n≤2×105),表示一个n个点的图,一开始没有边。节点编号从1到n。
然后输入m(1≤m≤2×105)和m个操作。
每个操作输入a、d、k(1≤a≤a+k×d≤n, 1≤d≤10,0≤k≤n),表示一个等差数列a,a+d,a+2d,…,a+k×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×d。然后遍历d和rd,对每个组内的区间v按照左右端点二次排序。对于同一类操作,如果某两个操作的点有交集,那么这两个操作等价于他们合并之后的操作,因为这两个操作中的任意一个点都可以先走到交集中的某个点,再走到另一个点。于是这两个操作并集中的所有点最后都会在同一个连通分量中。
所以,对于每一类操作,可以排序后使用双指针进行集合求并,得到若干个极大的操作,然后再使用并查集进行暴力连边。这样可以保证每个点最多只会被暴力操作10次。
复杂度分析
时间复杂度
集合合并的时间复杂度仅和边数有关,时间复杂度为O(mlogm)。每个节点暴力连边的时间复杂度为O(n×maxi∈[1,m]di),maxi∈[1,m]di=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;
}