「刷题」GERALD07加强版
2024-09-01 16:41:22
是LCT了。
首先我们不知道联通块怎么数。
然后颓标签知道了是LCT。
那么考虑一下怎么LCT搞。
有一个很普遍的思路大家也应该都知道，就是如何求一个区间中某种颜色的个数。
这个可以很简单的用主席树来实现对吧，只需要记录下来这种颜色上次出现的位置就可以了，然后在$[l,r]$中查询值在$[0,l-1]$中的数的个数。
然后联通块和这个有什么关系呢？
颜色的话为什么可以用这种方法代替呢？为了去重，而这道题中什么情况是所谓“重”的呢？
就是两条边链接了两个相同的集合的时候。
那么考虑以下一种算法。
用LCT维护生成树。动态加边，并查集维护联通性。
如果当前这条边链接的两个端点已经在一个集合中了，那么说明这条边可以替代掉之前的某一条边，记为$res[i]$那么这条边能够连接某两个集合的时候也就是在$[res[i]+1,i]$这个区间中，在LCT中查询最早的$res[i]$那么也就是当前这条边所能其作用的最早的端点，同时LCT删掉res[i]，link上i。
如果当前这条边链接的两个端点没有在一个集合中，直接link上i。
那么考虑一个区间的答案。
每增加一个新的可以链接这个联通块的边，那么n个集合会变成n-1个。
也就是说，答案就是n减去这些边中真正能够链接两个不再同一集合中端点的边的个数。
那么其实也就是这段区间中$res$值小于$l-1$的数的个数。
主席树维护即可。
得解。
最新文章
- Daily Scrum Meeting ——FifthDay(Beta)12.13
- Struts2 自定义拦截器
- [CCF] Z字形扫描
- coins_多重背包
- 利用python yielding创建协程将异步编程同步化
- C++ static_cast dynamic_cast reinterpret_cast const_cast转换
- mac 上iterm终端显示中文为乱码解决方案
- 10.10_魔兽账号,OSC代码托管演示,研究SQL别忘记了,git
- python加密解密
- CSS中定位position
- linux mint 下mysql中文支持问题
- Ubuntu 13.04 用户安装 gnome 3.8 桌面
- HTML5 Canvas、内联 SVG、Canvas vs. SVG
- Fix “Could not flush the DNS Resolver Cache: Function failed during execution” When Flushing DNS
- vue2.0 如何在hash模式下实现微信分享
- Client-Side Template Injection with AngularJS
- 外网访问内网SpringBoot
- 1分钟快速制作漂亮的H5本地记事本
- [模板][P4238]多项式求逆
- 关于二进制——lowbit运算