YbtOJ 794「cdq 分治 整体二分」奇度边集

(Updated: )
oi
,

题目链接：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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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;
}