[CF2020D] Connect the Dots 题解

aeiouaoeiu · 2024-10-05 10:11:58 · 题解

考虑 d=1 怎么做。实际上一次修改就是将一个区间合并到了一起。用并查集跳即可。

考虑只有一种 d 怎么做。实际上就是按编号除以 d 的余数分成了 d 种点。每次修改就将其中一种点的一段连续区间合并，仍然可以使用并查集跳。

考虑本题。直接开 d 种并查集即可。最后可以再用一个并查集，将每个并查集中 i 及其父亲合并，这样就将 d 个并查集合并了。

时间复杂度 \mathcal{O}(n\log n\cdot D)，其中 D=10，通过记录连通块编号最大点可以使用按秩合并或启发式合并，做到 \mathcal{O}(n\alpha(n)\cdot D)。

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef int ll;
typedef __int128 LL;
const ll maxn=200007,ee=1e18,p=998244353;
struct Dsu{
    ll fa[maxn];
    ll fid(ll x){for(;x^fa[x];x=fa[x]=fa[fa[x]]); return x;}
    void merge(ll x,ll y){
        x=fid(x),y=fid(y); if(x==y) return;
        if(x>y) fa[y]=x;
        else fa[x]=y;
    }
}dsu[11];
ll n,m,ans;
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll T=1; cin>>T;
    for(;T--;){
        cin>>n>>m; ans=0;
        for(int i=0;i<=10;i++) iota(dsu[i].fa+1,dsu[i].fa+1+n,1);
        for(int i=1,a,d,k,fr,ed;i<=m;i++){
            cin>>a>>d>>k; if(k==0) continue;
            fr=a,ed=a+d*k;
            for(int j=fr+d;j<=ed;j=dsu[d].fid(j+d)){
                dsu[d].merge(j-d,j);
                if(j+d>ed) break;
                dsu[d].merge(j,j+d);
            }
        }
        for(int j=1;j<=10;j++)for(int i=1;i<=n;i++) dsu[0].merge(dsu[j].fid(i),i);
        for(int i=1;i<=n;i++)if(dsu[0].fid(i)==i) ans++;
        cout<<ans<<"\n";
    }
    return 0;
}