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

P7457 [CERC2018] The Bridge on the River Kawaii

P7457 [CERC2018] The Bridge on the River Kawaii

题意

给你一个 \(n\) 个点初始没有边的无向图。有 \(q\) 个操作。

  1. 连边 \((u,v)\)。权值为 \(w\)
  2. 删边 \((u,v)\)
  3. 查询 \(u,v\) 之间权值最大值最小的路径的权值。

\(n,q \le 10^5, 0 \le w \le 10\)

保证任意时刻没有重边。

思路

发现 \(w\) 很小。所以把 \(w \le k(k \in [0,10])\) 的边建成一个图,建 \(11\) 个图。

维护这些图,每次查询就在每个图上都查一下。


对于一个图,我们需要知道任意两点是否连通。可以使用并查集维护。

但是有删边怎么办?可以使用可撤销并查集。

我们有套路的线段树分治 + 可撤销并查集做法。\(O(Vq\log^2q)\)

我们把询问按照时间排序,然后分治处理。

为了保证分治复杂度正确,我们其实是在时间轴上分治,而不是在询问序列上分治。这样可以保证分治区间的操作个数。

对每个分治区间,我们用可撤销并查集维护在这个区间内一直有效的边。

具体地,每条边在一段区间内有效。我们把这段区间在线段树上用 \(\log\) 个节点表示(类似线段树区间操作那样)。

当我们分治到这些节点时,就往并查集里加入这条边。当我们从这个节点回溯时,就从并查集撤销这条边。

对于非叶子分治区间 \([l,r]\)

  1. 往可撤销并查集里加入一些边。
  2. 递归左半区间和右半区间。
  3. 撤销刚刚加入的边。

对于叶子,如果这个叶子时查询,就可以查询一下 \(u,v\) 是否连通。

时间复杂度 \(O(Vq \log^2 q)\)

常数不太大,能过。


还有 lct 做法。

我们先离线地预处理出每条边的删除时刻。

维护每个图的生成树。用 lct 维护删边操作。

还有个问题,如果添加了一条新边 \((u,v)\),但是 \(u,v\) 已经在一个连通块里了。假如 \((u,v)\) 的删除时刻比较晚,我们需要用 \((u,v)\) 代替树上的某一条边。

我们可以贪心地找出 \(u,v\) 之间的路径的删除时间最早的边,并判断是否换掉它。

这样子复杂度就是 \(O(Vq \log q)\) 的。

但是我不会 lct。

code

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace wing_heart {constexpr int N=1e5+7;int n,q;struct edge{int u,v,w,l,r;}e[N];struct pii {int u,v;bool operator < (const pii b) const { return u==b.u ? v<b.v : u<b.u; }}que[N];int ans[N];map<pii,int> mp;int ecnt;vector<int> vec[N<<2];void insert(int u,int l,int r,int x) {if(l>=e[x].l && r<=e[x].r) return vec[u].push_back(x);int mid=(l+r)>>1;if(e[x].l<=mid) insert(u<<1,l,mid,x);if(mid+1<=e[x].r) insert(u<<1|1,mid+1,r,x);}int fa[N],siz[N];stack<pii> st;int find(int x) { return !fa[x] ? x : find(fa[x]); }bool merge(int u,int v) {u=find(u), v=find(v);if(u==v) return 0;if(siz[u]<siz[v]) swap(u,v);siz[u]+=siz[v]; fa[v]=u;st.push({u,v});return 1;}void back() {int u=st.top().u, v=st.top().v;st.pop();siz[u]-=siz[v], fa[v]=0;}void solve(int u,int l,int r,int lim) {int cnt=0;for(int x : vec[u]) if(e[x].w<=lim) if(merge(e[x].u,e[x].v)) ++cnt;if(l==r) {if(que[l].u && find(que[l].u) == find(que[l].v)) ans[l] = lim;} else {int mid=(l+r)>>1;solve(u<<1,l,mid,lim), solve(u<<1|1,mid+1,r,lim);}rep(i,1,cnt) back();}void main() {sf("%d%d",&n,&q);rep(i,1,q) {int op,u,v;sf("%d%d%d",&op,&u,&v);if(u>v) swap(u,v);++u, ++v;if(op==0) {int w;sf("%d",&w);e[++ecnt] = {u,v,w,i,q};mp[{u,v}]=ecnt;} else if(op==1) {e[mp[{u,v}]].r=i-1;} else {ans[i]=-1;que[i]={u,v};}}rep(i,1,ecnt) insert(1,1,q,i);rep(i,1,n) siz[i]=1;per(i,10,0) {solve(1,1,q,i);}rep(i,1,q) if(que[i].u) pf("%d\n",ans[i]);}
}
int main() {#ifdef LOCALfreopen("in.txt","r",stdin);freopen("my.out","w",stdout);#endifwing_heart :: main();
}
http://www.hskmm.com/?act=detail&tid=27816

相关文章:

  • 2025 年温控器厂家最新推荐排行榜:涵盖电子式/机械式/双恒温/紧凑型温控器等多类型,综合性能、创新与口碑的权威榜单
  • 2025 年 VI 设计企业最新推荐榜:优质机构深度解析,助力企业精准匹配优质品牌视觉解决方案
  • 【Linux基础知识系列:第一百三十九篇】使用Bash编写函数提升脚本功能 - 教程
  • 括号序列构造字典序最小化问题
  • C++ 性能优化:用 CRTP 搭建零开销编译期多态
  • Python 中包(Package)和模块(Module)的区别
  • Elasticsearch Enterprise 9.1.5 (macOS, Linux, Windows) - 分布式搜索和分析引擎
  • GIMP 3.0.6 发布 - 免费开源图像编辑器
  • Elasticsearch Enterprise 8.19.5 (macOS, Linux, Windows) - 分布式搜索和分析引擎
  • 2025 年国内丝杆升降机厂家最新推荐排行榜:滚珠 / 螺旋 / 蜗轮 / 同步 / 电动类型品牌核心优势深度解析
  • Linux设置分辨率(临时)
  • CAD 多个dwg文件合成一张图(无需插件)
  • 鸿蒙应用开发从入门到实战(十八):组件编程思想之代码复用
  • Gerkin+Pytest(python)建立自动化(BDD)
  • git克隆代码保留提交记录,从源仓库迁移到新仓库地址
  • ArcGIS 10.8 永久免费版安装包下载及安装教程!
  • OpenAI 发布 gpt-realtime-mini,成本降低 70%;Deepgram 发布转录和轮次检测融合 api丨日报
  • 2025年搜索式BI深度研究报告:核心功能、应用场景与产品选型
  • 2025 年光伏螺旋地桩厂家推荐:天津宏图新能源发展有限公司专业解决方案与设备优势
  • Ai元人文:部署模式构想——公共服务与用户消费
  • 基于Java+Springboot+Vue开发的旅游景区管理系统源码+运行步骤
  • MySQL从入门到熟练查询
  • 云之家提单反馈
  • Atcoder Beginner Contest 422
  • centos安装libgdiplus-6.1
  • RapidJSON 自定义内存分配器详解与实战 - 详解
  • 2025 最新推荐!云南旅游旅行社口碑排行榜,权威榜单助选靠谱服务商
  • 代码生成模型自我调试技术解析
  • 每日一题 ##1两数之和
  • python-Zipfile模块-常用代码