CF687D Dividing Kingdom II 题解

Description

给定一个 $n$ 个点、$m$ 条边的图，有 $q$ 次询问，每次询问一个 $[l,r]$ 的区间，求将 $n$ 个点分为两个部分后，编号在 $[l,r]$ 内的边中，两端点属于同一部分的边权最大值最小是多少。

Solution

转换一下题意，删去一些边使得剩下的图是一个二分图，使得删去的边权最大值最小。

上来看到最大值最小，立马想到二分答案，每次二分一个边权 $mid$，将所有边权大于 $mid$ 的加入图中，用扩展域并查集判断是否是二分图。

时间复杂度 $O(q\log m(n+m\alpha (n)))$。

但是你发现 $O(\log m)$ 是没必要的，先将边按边权从大到小排序，若编号属于 $[l,r]$ 就加入图中，如果加完这条边变奇图了那么这条边的边权就是答案。

时间复杂度 $O(q(n+m\alpha (n)))$，由于 CF的神仙机子以及 $6$ 秒的实现可以暴力通过。

考虑如何优化，发现每一次加入边后的图实际上只有 $O(n)$ 条边会对下次加边造成影响，即一些树边（可能是森林）和可能有的一条边权最大的非树边（当前答案），它们可以代表当前的图，同时一些边在多组询问中都被并入一次，而将询问上到线段树上就可以避免。

所以我们开一棵线段树，节点 $[l,r]$ 表示将编号 $[l,r]$ 的边并完后能代表这个图的 $O(n)$ 条边，同时按边权从大到小排序，合并时先归并排序，将左右儿子的代表边集和在一起，然后求出新图的代表边集，建树复杂度为 $O(m\log m\alpha (n))$。

查询时将 $[l,r]$ 的代表边集暴力求答案，复杂度 $O(qn\alpha (n)\log m)$。

还可以继续，将询问离线离散化，树上节点 $[l,r]$ 表示 $[b_l,b_{r+1})$ 区间的代表边集，其中 $b$ 是离散数组。

记得离散询问 $[l,r]$ 时，离散 $l$ 和 $r+1$，查询时取出 $[c_l,c_{r+1}-1]$ 的代表集暴力即可，其中 $c_i$ 表示 $i$ 离散后的编号，若询问中没有 $1$ 和 $m$，记得加进离散。

时间复杂度 $O(m\log q\alpha (n)+qn\alpha (n)\log q)$。

Code

#include<bits/stdc++.h>
using namespace std;
#define ls x<<1
#define rs x<<1|1
struct edge{int x,y,z;
}e[1000010];
bool cmp(edge x,edge y){return x.z>y.z;
}
#define ve vector<edge> 
int n,m,q,tot;
int b[6060],siz[2020],fa[2020];
ve tr[4000040];
struct que{int l,r;
}qu[3030];
int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);
}
bool uni(int x,int y){int fx=find(x),fy=find(y);if(fx==fy) return 0;if(siz[fx]>siz[fy]) swap(fx,fy);siz[fy]+=siz[fx];fa[fx]=fy;return 1;
}
void reset(int x){fa[x]=x,fa[x+n]=x+n;siz[x]=1,siz[x+n]=1;
}
pair<ve,int> solve(ve tmp){ve ans;for(auto x:tmp){reset(x.x),reset(x.y);}for(auto i:tmp){int x=find(i.x),y=find(i.y);if(x!=y){if(uni(i.x,i.y+n)&&uni(i.y,i.x+n)){ans.push_back(i);}}else{ans.push_back(i);return {ans,i.z};break;}}return {ans,-1};
}
ve merge(ve l,ve r){ve tmp;int fl1=0,fl2=0;while(fl1<l.size()&&fl2<r.size()){if(cmp(l[fl1],r[fl2])){tmp.push_back(l[fl1++]);}else{tmp.push_back(r[fl2++]);}}while(fl1<l.size()) tmp.push_back(l[fl1++]);while(fl2<r.size()) tmp.push_back(r[fl2++]);auto ans=solve(tmp);return ans.first;
}
void build(int x,int l,int r){if(l==r){ve tmp;for(int i=b[l];i<b[l+1];i++){tmp.push_back(e[i]);}sort(tmp.begin(),tmp.end(),cmp);auto ans=solve(tmp);tr[x]=ans.first;return ;}int mid=l+r>>1;build(ls,l,mid),build(rs,mid+1,r);tr[x]=merge(tr[ls],tr[rs]);
}
ve query(int x,int l,int r,int L,int R){if(l>=L&&r<=R){return tr[x];}int mid=l+r>>1;if(R<=mid) return query(ls,l,mid,L,R);if(L>=mid+1) return query(rs,mid+1,r,L,R);return merge(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));
}
int main(){ios::sync_with_stdio(0);cin.tie(nullptr);cin>>n>>m>>q;for(int i=1;i<=m;i++){cin>>e[i].x>>e[i].y>>e[i].z;}for(int i=1;i<=q;i++){cin>>b[++tot]>>b[++tot];b[tot]++;qu[i]={b[tot-1],b[tot]};}b[++tot]=1;sort(b+1,b+1+tot);tot=unique(b+1,b+1+tot)-b-1;b[tot+1]=m+1;  //注意细节build(1,1,tot);for(int i=1;i<=q;i++){int l=lower_bound(b+1,b+1+tot,qu[i].l)-b;int r=lower_bound(b+1,b+1+tot,qu[i].r)-b-1;ve tmp=query(1,1,tot,l,r);int ans=solve(tmp).second;cout<<ans<<'\n';}return 0;
}