P7457 [CERC2018] The Bridge on the River Kawaii
题意
给你一个 \(n\) 个点初始没有边的无向图。有 \(q\) 个操作。
- 连边 \((u,v)\)。权值为 \(w\)。
- 删边 \((u,v)\)。
- 查询 \(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]\)。
- 往可撤销并查集里加入一些边。
- 递归左半区间和右半区间。
- 撤销刚刚加入的边。
对于叶子,如果这个叶子时查询,就可以查询一下 \(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();
}