YbtOJ 794「cdq 分治 整体二分」奇度边集
整体 二分 YbtOJ 分治
2023-06-13 09:12:49 时间
YbtOJ 794「cdq 分治 整体二分」奇度边集
题目链接:YbtOJ #794
小 A 有一张 n 个点的图,他会依次往里面加入 m 条带权边。
每加入一条边之后,小 A 都要先判断是否存在一个边集使得所有点度数都是奇数,若存在则求出所有符合要求的边集中 最大边权 的 最小值,若不存在则输出 -1
。
1\le n\le10^5,1\le m\le 3\times10^5,0\leq v\leq 10^9。
Solution
发现“所有点度数都是奇数”等价于“这个图中只存在大小为偶数的连通块”。
简单证明:
- 必要性:假设存在一个奇数大小的连通块,由于每个点的度数都为奇数,所有度数之和也必定为奇数,而每条边对总度数贡献为 2,故总度数必然为偶数,与假设矛盾。所以仅存在偶数大小的连通块。
- 充分性:每个偶数大小的连通块,随便跑个生成树,从底往上扫一遍,如果该节点的儿子连上来的边数为偶数,就与其父亲相连,我们发现这样构造可以满足除了根以外的点限制,而又由所有点度数之和为偶数,其他节点数量为奇数,度数也为奇数,所以根的度数也为奇数。
转换为题意后,考虑权值从小到大加边,如果用并查集维护一下奇连通块的个数,我们就可以完成了一个静态的题目。
下面考虑如何扩展到动态。
注意到一条边如果进入时没有进入最优边集,那么就再也不会进入。
也就是说每条边会有一个影响范围。
考虑线段树分治,每访问到一个叶子,直接后移指针,添加边,直到合法为止。显然此时就是这条边的影响范围结束位置,而每条边的出现位置显然,于是就做好了。
但我们发现这是一个边分治一边 cover 的处理过程,直接线段树分治起来可能会有点小问题,因为这个时间点上 cover 上的边不知道什么时候撤回掉。
这也很简单啊,只 cover 到当前时间减一就可以了,这个点上 cover 上的边在这个点直接撤回就完事了。
这个算法的原理也很好理解:
我们每次在叶子节点找答案,祖先节点上 cover 上的时间戳必然合法,在这个点上 cover 上的边也会因为判断而只加起始时间在当前时间点之前的边。
原本我们的时间复杂度因为每一次暴力加边而变得不可接受。
而通过计算决策的影响范围与将这些范围线段树分治,就减少了大量的重复计算。
Code
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=3e5+10,P=1e5+10;
int n,m,fa[P],s[P],Ans[N],p;
struct Edge{int x,y,z,id;}e[N];
I bool cmp(Cn Edge& x,Cn Edge& y){return x.z<y.z;}
I int GF(CI x){return x==fa[x]?x:fa[x]=GF(fa[x]);}
struct node{int x,y,v;};
vector<node> stk;
#define pb push_back
I void M(RI x,RI y){(x=GF(x))^(y=GF(y))&&(s[x]<s[y]&&(swap(x,y),0),s[x]&1&&s[y]&1?n-=2,stk.pb((node){x,y,2}):stk.pb((node){x,y,0}),s[x]+=s[y],fa[y]=x,0);}
I void R(CI o){W(stk.size()^o) s[stk.back().x]-=s[stk.back().y],fa[stk.back().y]=stk.back().y,n+=stk.back().v,stk.pop_back();}
vector<int> G[N<<2];
class SegmentTree{
private:
#define mid (l+r>>1)
#define PT CI x=1,CI l=1,CI r=m
#define LT x<<1,l,mid
#define RT x<<11,mid+1,r
I void U(CI L,CI R,CI v,PT){if(L>R) return ;if(L<=l&&r<=R) return void(G[x].pb(v));L<=mid&&(U(L,R,v,LT),0),R>mid&&(U(L,R,v,RT),0);}
public:
I void Q(PT){
RI o=stk.size();for(auto i:G[x]) M(e[i].x,e[i].y);G[x].clear();
if(l==r){W(n&&p<m) e[++p].id<=l&&(M(e[p].x,e[p].y),U(e[p].id,l-1,p),0);Ans[l]=n?-1:e[p].z;}
else Q(RT),Q(LT);R(o);
}
}T;
int main(){
freopen("edges.in","r",stdin),freopen("edges.out","w",stdout);
RI i;for(read(n,m),i=1;i<=n;i++) fa[i]=i,s[i]=1;
for(i=1;i<=m;i++) read(e[i].x,e[i].y,e[i].z),e[i].id=i;
for(sort(e+1,e+m+1,cmp),T.Q(),i=1;i<=m;i++) writeln(Ans[i]);return 0;
}
相关文章
- 0-STM32G070+CH395Q基本控制篇(自建物联网平台)-整体运行测试-STM32+CH395Q连接MQTT服务器
- Paxos 为什么可以保证整体一致性?
- 服务器硬盘整体ghost,ghost备份整个硬盘| 全盘镜像ghost步骤[通俗易懂]
- QQ频道(内测版)整体使用简谈
- 【信管3.1】项目整体管理概念与过程
- 【应急能力提升7】整体总结与提升
- SpringCloud之整体聚合父工程
- 【链表习题集1】整体和局部反转链表&同频和快慢指针&合并链表
- 云ERP系统实施的整体流程是什么?
- 英特尔第四代至强来袭:AI性能提升10倍!整体能效提升2.9倍!
- DDD实战之七: 战术设计、整体流程与首次冲刺
- 【五线谱】高低八度标记 ( 高八度标记 | 标记范围的音符整体提升一个八度 | 低八度标记 | 标记范围的音符整体降低一个八度 )
- 【Unity3D】游戏物体操作 ③ ( 旋转操作 | 旋转工具 | 基本旋转 | 设置旋转属性 | 增量旋转 | 缩放操作 | 轴向缩放 | 整体缩放 | 操作工具切换 | 操作模式切换 )
- 《数字中国建设整体布局规划》发布,想抓住下一个风口?先来学学这门课!
- ABAP基础一:ALV基础之ALV的整体结构详解编程语言
- 如何通过gzip和nginx来提高网站打开速度及整体性能