并查集-方法论-题解

区间覆盖问题

染色体染色，问每个的最后颜色是什么

• 参考
  给定 M MM 次染色序列，问最后所有位置的颜色是什么？如果从前向后考虑，后边的染色会覆盖之前的一种染色，可以倒着考虑，如果一段区间已经染色就不再被染色了 (每个位置只会被染色一次) ，然后跳过一些状态，进行优化。
  重要判据: fa[i] = i 表示这个节点 / 物品，还没有出现过，或者还没有被染色过

  int n,m,p,q;
  int fa[1000010];
  int a[1100000];
  int ans[1100000];
  int find(int x){// 找到从x开始的右边的第一个没有被染色的元素
      return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
  }
  
  void solve(){
      cin>>n>>m>>p>>q;
      for(int i=1;i<=1000010;i++){
          fa[i] = i;
      }
      while(m){
          int l = (m*p+q)%n+1;
          int r = (m*q+p)%n+1;
          if(l>r)swap(l,r);
          // 【l，r】
          int x = find(l);
          while(x<=r){
              // [l,x]
              ans [x] = m;
              fa[x] = find(x+1);
              x = find(x);
          }
          m -- ; // 容易错
      }
      for(int i=1;i<=n;i++){
          cout<<ans[i]<<endl;
      }
  }

密码生成

• 参考

  #include <cfloat>
  #include <iostream>
  #include <vector>
  #include <map>
  #include <numeric>
  #include <algorithm>
  using namespace std;
  
  int find(int start, vector<int>& pa)
  {
  	// 这里find(pa[start], pa)是关键；find(start) 肯定不行；
  	// find(start+1)，可以但是复杂度太高
  	return pa[start] == start ? start : pa[start] = find(pa[start], pa);
  }
  
  int main() {
  int N, M;
  cin >> N >> M;
  int mod = 100000009;
  long long ans = 0;
  vector<int> pa(N+1, 0);
  vector<int> nums(N, 0);
  iota(pa.begin(), pa.end(), 0);
  
  int L, R;
  
  vector<pair<int, int>> rec;
  
    
  
  for (int __ = 0; __ < M; __++)
  
  {
  
  int l, r;
  
  cin >> l >> r;
  
  rec.push_back({l, r});
  
  }
  
  while (M > 0)
  
  {
  
  L = rec[M-1].first;
  
  R = rec[M-1].second;
  
  if (L > R) swap(L, R);
  
    
  
  int x = find(L, pa);
  
  while (x <= R)
  
  {
  
  nums[x] = M;
  
  // ans += (1ll * x * M)%mod;
  
  pa[x] = find(x+1, pa);
  
  x = find(x, pa);
  
  }
  
  M--;
  
  }
  
    
  
  for (int i = 1; i < N; i++)
  
  {
  
  ans += (1ll * i * nums[i])%mod;
  
  ans %= mod;
  
  }
  
    
  
  cout << ans;
  
  }
  
  // 64 位输出请用 printf("%lld")