当前位置: 首页 > news >正文

倍增并查集学习笔记

学完板子即可开始水紫题


倍增并查集,可以在 \(O(m log^2 n)\) 的时间复杂度内求解 \(m\) 个诸如此类的合并问题:

\[\forall \,\,\,\,\, 0 \leq i \leq k \, , \, merge(x+i,y+i) \]

就真的是倍增和并查集的结合体,而不像 \(dsu\,on\,tree\) 那样挂个名头

对于这一类问题,我们可以考虑把合并区间进行二进制拆分

給所有长度为 \(2^i\) 的区间开一个并查集(以下统一称为 \(i\) 级并查集)

代表若在 \(i\) 级的并查集中,元素 \(u,v\) 属于同一连通块,则

\[\forall \,\,\,\,\, 0 \leq i < 2^i \, , \, x+i,y+i \text{在同一连通块中} \]

显然这样的东西非常好维护

再考虑最后怎么把它转成正常并查集的样子

若我想把第 \(i\) 级的并查集传到第 \(i-1\) 级,若 \(p\)\(i\) 级并查级中 \(q\) 的祖先,那么在 \(i-1\) 级并查集中应执行以下操作:

\[merge(q,p),merge(q+2^{i-1},p+2^{i-1}) \]

操作大多数都和 \(st\) 表差不多

luogu P3295

CODE
#include<bits/stdc++.h>
#define usetime() (double)clock () / CLOCKS_PER_SEC * 1000.0
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int mod=1e9+7;
void read(int& x){char c;bool f=0;while((c=getchar())<48) f|=(c==45);x=c-48;while((c=getchar())>47) x=(x<<3)+(x<<1)+c-48;x=(f ? -x : x);
}
int find_f(int u,int* f){if(f[u]==u) return u;else return f[u]=find_f(f[u],f);
}
void merge(int u,int v,int* f){u=find_f(u,f),v=find_f(v,f);if(u!=v) f[u]=v;
}
int n,m;
int f[21][maxn];
int main(){read(n),read(m);int l1,r1,l2,r2;for(int i=1;i<=n;i++){for(int j=0;j<=20;j++){f[j][i]=i;}}for(int i=1;i<=m;i++){read(l1),read(r1),read(l2),read(r2);for(int j=20;j>=0;j--){if(l1+(1<<j)-1<=r1){merge(l1,l2,f[j]);l1+=(1<<j),l2+=(1<<j);}}}for(int i=20;i>=1;i--){for(int l=1,r=(1<<i);r<=n;l++,r++){int tar=find_f(l,f[i]);merge(l,tar,f[i-1]),merge(l+(1<<(i-1)),tar+(1<<(i-1)),f[i-1]);}}int av=find_f(1,f[0]);LL ans=1;for(int i=1;i<=n;i++){//cout<<find_f(i,f[0])<<' ';if(i==f[0][i]){if(f[0][i]==av) ans=ans*9%mod;else ans=ans*10%mod;}}//cout<<endl;printf("%lld",ans);return 0;
}
//^o^
http://www.hskmm.com/?act=detail&tid=31107

相关文章:

  • 两数相加-leetcode
  • CF2147E
  • 线程共享区域
  • ZR 2025 NOIP 二十连测 #1
  • 运行时数据区
  • work1
  • 2025 年液压机厂家推荐榜:伺服/小型/大型/数控/液压机厂家口碑推荐,品质可靠 聚焦智能适配,助力企业高效生产
  • 快速上手!山海鲸 4 种高频数据接入方式
  • AI赋能,重塑未来招聘:深度解析易路AI人岗匹配解决方案
  • 2025高级语言程序设计第一次作业lcr
  • luogu 个人主页
  • D230809E. 勇敢的阿乐
  • 解码Linux文件IO之标准IO
  • 10.14 CSP-S模拟31 改题记录
  • 高级程序语言第一次作业
  • 安装devc++过程的分享以及问题的记录
  • Linux之线程池 - 指南
  • zlog1
  • LlamaIndex检索调优实战:分块、HyDE、压缩等8个提效方法快速改善答案质量
  • 动火作业风险早预警!AI + 热成像技术筑牢防火安全线
  • 解题报告-P5664 [CSP-S2019] Emiya 家今天的饭
  • object类
  • Day 10
  • 2025 年生态格宾网厂家推荐榜:格宾网石笼/格宾网护坡/格宾网挡墙/格宾网网箱厂家推荐,聚焦工程安全与生态保护,助力基建项目高效落地
  • 时序博弈算法荣获时间检验奖
  • 背叛 仇恨 消极 如刀子刺穿了铁心 嘲笑 嗤之以鼻 漠然后只剩下孤寂
  • STM32主控芯片硬件设计总结
  • 亚马逊因暗黑模式订阅设计支付25亿美元和解金
  • P6645 [CCO 2020] Interval Collection
  • 2025年排烟风机厂家推荐榜:混流风机|管道风机|排烟风机|离心风机|轴流风机|轴流风机厂家,专注高效消防与节能,助力多行业绿色升级