Post

启发式合并

Posted
By 11 min read

一般启发式合并本质

小集合合并到大集合 时间复杂度: $ O(nlogn) $

P3201 [HNOI2009] 梦幻布丁

题目描述

$n$ 个布丁摆成一行，进行 $m$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。

例如，颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色.

输入格式

第一行是两个整数，分别表示布丁个数 $n$ 和操作次数 $m$。
第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个布丁的颜色 $a_i$。
接下来 $m$ 行，每行描述一次操作。每行首先有一个整数 $op$ 表示操作类型：

  • 若 $op = 1$，则后有两个整数 $x, y$，表示将颜色 $x$ 的布丁全部变成颜色 $y$。
  • 若 $op = 2$，则表示一次询问。

输出格式

对于每次询问，输出一行一个整数表示答案。

样例 #1

样例输入 #1

1
2
3
4
5

4 3
1 2 2 1
2
1 2 1
2

样例输出 #1

1
2

3
1

提示

样例 1 解释

初始时布丁颜色依次为 $1, 2, 2, 1$，三段颜色分别为 $[1, 1], [2, 3], [4, 4]$。
一次操作后，布丁的颜色变为 $1, 1, 1, 1$，只有 $[1, 4]$ 一段颜色。

数据规模与约定

对于全部的测试点，保证 $1 \leq n, m \leq 10^5$，$1 \leq a_i ,x, y \leq 10^6$。

提示

请注意，不保证颜色的编号不大于 $n$，也不保证 $x \neq y$，$m$ 不是颜色的编号上限。

思路

  • 两种颜色看作两个集合，利用启发式合并实现两种颜色合并
  • 维护段数，左右两边颜色不同(一边不同就多一条边，反之亦然)
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

    set<int> S[1000010];
int ans;
int n,m;
void merge(int x,int y){
  if(x==y)return;
  if(S[x].size()>S[y].size())swap(S[x],S[y]);
  for(auto i:S[x])ans-=S[y].count(i-1)+S[y].count(i+1);
  for(auto i:S[x])S[y].insert(i);
  S[x].clear();
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin>>n>>m;
  for(int i=1,x;i<=n;i++){
      cin>>x;
      if(!S[x].count(i-1))ans++;
      S[x].insert(i);
  }
  while(m--){
      int op;
      cin>>op;
      if(op==2)cout<<ans<<"\n";
      else{
          int x,y;
          cin>>x>>y;
          merge(x,y);
      }
  }
}

    树上启发式合并(dsu on tree)

    CF600E Lomsat gelral

    题意：
    一棵树每个节点有一种颜色，某个节点的主导颜色为该子树下颜色数量最多的颜色编号，求每个节点的主导颜色和 思路：

  • 每遍历完一颗子树的点，就要把最大值清空(避免影响另一颗子树的计算)
  • 当算完所有子节点后，就要统计当前点，需要在遍历一次子节点将颜色加回来
  • 可以发现遍历的最后一棵子树不用清空
  • 将重儿子作为最后一次遍历的子树
  • 每个轻儿子被遍历的次数为到根节点轻边的数
  • 对于一条轻边，$ siz_{重儿子}>=siz_{轻儿子} $ ,因此轻边最多$ logn $ 条
  • 时间复杂度: $ O(nlogn) $
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

    int color[N],siz[N],son[N],cnt[N];
vector<int> adj[N];
ll ans[N];
ll sum,mx,n;
void dfs_son(int u,int fa){
  siz[u]=1;
  for(auto v:adj[u]){
      if(v==fa)continue;
      dfs_son(v,u);
      siz[u]+=siz[v];
      if(siz[v]>siz[son[u]])son[u]=v;
  }
}
void update(int u,int fa,int sign,int pson){//将u子树的颜色加(减)到集合
  int c=color[u];
  cnt[c]+=sign;
  if(cnt[c]>mx)mx=cnt[c],sum=c;
  else if(cnt[c]==mx)sum+=c;
  for(auto v:adj[u]){
      if(v==fa||v==pson)continue;
      update(v,u,sign,pson);
  }
}
void dfs(int u,int fa,int op){
  for(auto v:adj[u]){
      if(v==fa||v==son[u])continue;
      dfs(v,u,0);
  }
  if(son[u])dfs(son[u],u,1);
  update(u,fa,1,son[u]);//更新除重儿子树外的点
  ans[u]=sum;
  if(!op)update(u,fa,-1,0),sum=mx=0;//当前节点为轻儿子，所有节点删除
}
void solve(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>color[i];
  for(int i=1;i<n;i++){
      int u,v;
      cin>>u>>v;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  dfs_son(1,0);
  dfs(1,0,1);
  for(int i=1;i<=n;i++)cout<<ans[i]<<" \n"[i==n];
}

    CF570D Tree Requests

    题意：
    给定一棵树，每个节点有个字母，有m次询问
    每次询问子树v内深度为k的节点能否组成回文串
    思路：

  • 判断一些字符是否能组成回文串，只需看字符出现数量是否小于等于1
  • 与深度有关，考虑启发式合并
  • $ nums_{i,j} 表示深度为i字母为j的数量 $
  • 将询问离线下来，每次更新完当前节点看是否有询问，更新答案即可
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

    struct Q{
  int pos,dep;
};
int n,m;
vector<int> adj[N];
vector<Q> q[N];
int dep[N],siz[N],son[N],ans[N];
int nums[N][26];
string s;
int have;
void dfs_son(int u,int fa){
  siz[u]=1;
  dep[u]=dep[fa]+1;
  for(auto v:adj[u]){
      dfs_son(v,u);
      siz[u]+=siz[v];
      if(siz[v]>siz[son[u]])son[u]=v;
  }
}
void update(int u,int sign,int pson){
  int x=s[u]-'a';
  if(nums[dep[u]][x]&1)have--;
  nums[dep[u]][x]+=sign;
  if(nums[dep[u]][x]&1)have++;
  for(auto v:adj[u]){
      if(v==pson)continue;
      update(v,sign,pson);
  }
}
void dfs(int u,int op){
  for(auto v:adj[u]){
      if(v==son[u])continue;
      dfs(v,0);
  }
  if(son[u])dfs(son[u],1);
  update(u,1,son[u]);
  for(auto [pos,d]:q[u]){
      int have=0;
      for(int j=0;j<26;j++){
          have+=nums[d][j]&1;
      }
      ans[pos]=(have<=1);
  }
  if(!op)update(u,-1,0);
}
void solve(){
  cin>>n>>m;
  for(int i=2;i<=n;i++){
      int x;
      cin>>x;
      adj[x].push_back(i);
  }
  cin>>s;
  s=" "+s;
  dfs_son(1,0);
  for(int i=1;i<=m;i++){
      int x,y;
      cin>>x>>y;
    
      q[x].push_back({i,y});
  }
  dfs(1,1);
  for(int i=1;i<=m;i++)cout<<(ans[i]?"Yes\n":"No\n");
}

    CF246E(树上启发式,线段树合并)

    给定一片森林，每次询问一个节点的 K-Son 共有个多少不同的名字。一个节点的 K-Son 即为在该节点子树内的，深度是该节点深度加 K 的节点。

    前置题目

    P1972 [SDOI2009] HH的项链(在序列上的做法)

    给定一个序列，每次询问区间内有多少个不同的数

    做法1：树状数组

  • 可以发现若左端点恒为1,则我们只关心每个数最后出现的位置(产生贡献的位置)
  • 因此对每个询问按r排序，当枚举到当前询问的r位置时计算答案
  • 用树状数组维护前缀和，每次把前一个出现的位置减1，当前位置加1
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

    struct ANS{
  int l,r,val,pos;
  bool operator<(const ANS&tmp)const{
      return r<tmp.r;
  }
} ans[N];
int a[N],n,m,c[N];
map<int,int> pre;
void add(int x,int y){
  for(int i=x;i<=n;i+=lowbit(i))c[i]+=y;
}
int query(int x){
  int ans=0;
  for(int i=x;i>0;i-=lowbit(i)){
      ans+=c[i];
  }
  return ans;
}
void solve(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i];
  cin>>m;
  for(int i=1;i<=m;i++){
      cin>>ans[i].l>>ans[i].r;
      ans[i].pos=i;
  }
  sort(ans+1,ans+m+1);
  for(int i=1,j=1;j<=m;i++){
      if(pre[a[i]])add(pre[a[i]],-1);
      add(i,1);
      pre[a[i]]=i;
      while(i==ans[j].r){
          ans[j].val=query(ans[j].r)-query(ans[j].l-1);
          j++;
      }
  }
  vector<int> res(m+1);
  for(int i=1;i<=m;i++)res[ans[i].pos]=ans[i].val;
  for(int i=1;i<=m;i++)cout<<res[i]<<"\n";
}

    做法2：可持久化线段树

    从左到右建不同的版本，和之前一样维护最后出现的数的贡献，询问l,r即在r的版本询问该区间和，但是数据过大tle了

    CF208E Blood CousinsCD

    $ 定义 p级表亲为在同一深度下，公共祖先为第p个祖先的点 $
    每次询问每个点的p级表亲

    做法1：DSU

    将每个询问的点的对应祖先找出来，离线 问题转变为在u子树下节点深度为d的节点数(记得减1)

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

    struct Q{
  int pos,dep;
};
vector<int> adj[N];
vector<Q> q[N];
int n,m,par[N][30],dep[N],siz[N],son[N],nums[N],ans[N];
void dfs_son(int u,int fa){
  if(!u)dep[u]=0;
  else dep[u]=dep[fa]+1;
  par[u][0]=fa;   
  for(int i=1;i<=log2(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1];
  siz[u]=1;
  for(auto v:adj[u]){
      dfs_son(v,u);
      siz[u]+=siz[v];
      if(siz[v]>siz[son[u]])son[u]=v;
  }
}
void update(int u,int sign,int pson){
  nums[dep[u]]+=sign;
  for(auto v:adj[u]){
      if(v==pson)continue;
      update(v,sign,pson);
  }
}
void dfs(int u,int op){
  for(auto v:adj[u]){
      if(v==son[u])continue;
      dfs(v,0);
  }
  if(son[u])dfs(son[u],1);
  update(u,1,son[u]);
  for(auto [pos,d]:q[u]){
      ans[pos]=nums[d]-1;
  }
  if(!op)update(u,-1,-1);
}
void solve(){
  cin>>n;
  for(int i=1;i<=n;i++){
      int x;
      cin>>x;
      adj[x].push_back(i);
  }
  dfs_son(0,-1);
  cin>>m;
  for(int i=1;i<=m;i++){
      int x,y;
      cin>>x>>y;
      int yy=y;
      for(int i=25;i>=0;i--){
          if(par[x][i]>0&&y>=(1<<i))x=par[x][i],y-=(1<<i);
      }
      if(!y)q[x].push_back({i,dep[x]+yy});
  }
  dfs(0,1);
  for(int i=1;i<=m;i++)cout<<ans[i]<<" ";
}

    做法2：二分

    回到本题

    直接dsu了，有dfs+树状数组+二分的做法

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

    struct Q{
  int pos,dep;
};
set<int> nums[N*2];
map<string,int> vis;
int idx,n,m,a[N],ans[N];
vector<int> adj[N];
vector<Q> q[N];
int dep[N],son[N],siz[N];
void dfs_son(int u,int fa){
  if(!u)dep[u]=0;
  else dep[u]=dep[fa]+1;
  siz[u]=1;
  for(auto v:adj[u]){
      dfs_son(v,u);
      siz[u]+=siz[v];
      if(siz[v]>siz[son[u]])son[u]=v;
  }
}
void update(int u,int sign,int pson){
  if(sign>0){
      if(!nums[dep[u]].count(a[u]))nums[dep[u]].insert(a[u]);
  }
  else nums[dep[u]].clear();
  for(auto v:adj[u]){
      if(v==pson)continue;
      update(v,sign,pson);
  }
}
void dfs(int u,int op){
  for(auto v:adj[u]){
      if(v==son[u])continue;
      dfs(v,0);
  }
  if(son[u])dfs(son[u],1);
  update(u,1,son[u]);
  for(auto [pos,d]:q[u]){
      ans[pos]=nums[d].size();
  }
  if(!op)update(u,-1,-1);
}
void solve(){
  cin>>n;
  for(int i=1;i<=n;i++){
      string s;
      cin>>s;
      if(vis[s])a[i]=vis[s];
      else a[i]=++idx,vis[s]=a[i];
      int x;
      cin>>x;
      adj[x].push_back(i);
  }
  cin>>m;
  dfs_son(0,-1);
  for(int i=1;i<=m;i++){
      int x,y;
      cin>>x>>y;
      q[x].push_back({i,dep[x]+y});
  }
  dfs(0,1);
  for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}
算法, 启发式合并
启发式合并
This post is licensed under CC BY 4.0 by the author.