Codeforces 938G（cdq分治+可撤销并查集+线性基）
2024-09-30 13:41:48
题意：
有一个无向连通图，支持三个操作：
1 x y d ： 新建一条x和y的无向边，长度为d
2 x y ：删除x和y之间的无向边
3 x y ：询问x到y的所有路径中（可以绕环）最短的是多少（路径长度是经过所有边的异或）
n,m,q<=2e5
分析：
如果没有加边和删边操作，那么就是个经典的线性基问题
我们可以先弄出一个树，然后非树边就形成环，把环丢进线性基就可以了
现在有了加边和删边操作，我们可以考虑每条边的存活时间，对这个时间进行cdq分治，那么就只有加边没有删边了
然后再离线处理询问即可
可以用线段树实现更加简单
具体实现的时候，加边操作即是加了一些边到并查集里面，所以退出时撤销掉就行了
至于base，直接拿数组存下来，覆盖即可
时间复杂度O(nlog^2n)
最新文章
- 【MongoDB for Java】Java操作MongoDB
- POJ1523 SPF[无向图割点]
- .Net Framework 3.5, 3.5 sp1 中文版离线安装
- 后台子线程（非主线程）更新UI引起的警告
- 用"僵尸对象"调试内存管理问题
- 汉字转拼音Pinyin4j工具（C#、Java都可用）
- java与c++的访问权限的问题
- HBase Client API使用（二）---查询及过滤器
- 有利于SEO的DIV+CSS规范小结
- CSSREM插件
- Charles 抓包工具使用部分问题总结
- 用Python满足满足自己的“小虚荣”
- 相约南湖，南京都昌信息亮相南湖HIT论坛
- CAD{绘制坡道）（绘制楼梯）5.26
- Python3学习之路~4.1 列表生成式、生成器
- 第03章：MongoDB启动参数说明
- 【转】UICollectionView使用介绍
- Common Gateway Interface Python CGI编程
- TP5使用Composer安装phpoffice/phpspreadsheet，导出Excel文件
- 解决shell命令"** is not in the sudoers file..."错误