CF603E Pastoral Oddities

$\color{deeppink}link$

$n$ 个点，动态加入 $m$ 条边，加入一条边后查询是否存在一个边集使得每个点的度数为奇数。

考虑条件限制的本质。

每个点的度数为奇数，但是一个连通块中的总度数是偶数，那么若这个连通块有奇数个点，则这个联通块必不合法。

若连通块的点个数是偶数，那可以先求出一个生成树，从叶子向上贪心，根据向儿子的连边情况判断是否连这条边即可构造。

然后考虑一个静态的问题。

将边从小到大排序，用 Kruskal 加边，直到奇数个点的连通块个数为 $0$ 为止，注意到多加边不会对答案造成影响。

这是一个没有前途的静态做法。

考虑到动态加边十分麻烦，还要支持动态排序，那么可以用时间回溯大法，先将所有的边加进去，然后从后面开始枚举，然后删边。

考虑到一条边在排出边集之后（或者没加入边集）永远不会再次加入到边集中，那么可以维护一个没加入边集的边，从小到大排序，维护一个 $pos$ 指针，在删掉一条边之后就将 $pos$ 向后移，直到满足条件为止。

这其实就是加边、删边，维护联通情况的问题，直接来个可撤销的并查集显然无法维护联通性，然后错过一大堆信息。

这其实可以套用 二分图 的套路，用 LCT 维护最小的删除时间和边的编号，若要删的边正好是 LCT 中标记的那条边时，将 $pos$ 向后移，直到满足条件为止。否则跳过。

每一时刻的答案是 $val_{pos}$。时间是 $O(n\log n)$ 虽然常数巨大。

同样地，二分图 和这道题也都可以用线段树分治做。

具体做法是维护每条边的影响范围，从后面向前分治。

还是将所有边按照权值从小到大排序，枚举到叶子且当前不满足条件时，将 $pos$ 向后移直到满足条件为止，同时将枚举到的边 $i$ 在线段树上的 $[time_i,l-1]$ 加上 $i$，因为这代表着这条边会在 $l+1$ 处被排出边集。跑到叶子时答案还是 $val_{pos}$。时间依旧是 $O(m\log m\log n)$。

代码（线段树分治的版本）

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+500,M=6e5+50;

struct node
{
	int u,v,w,tim;
	
	inline friend bool operator<(node a,node b)
	{
		return a.w<b.w;
	}
}e[N];

struct wty
{
	int u,v;
}k[N];vector<wty>edge[N];

int n,m,pos=1,fa[N],siz[N],num,ans[N],tot;

#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)

inline void add(int x,int l,int r,int L,int R,wty d)
{
	if(L<=l&&R>=r)return void(edge[x].push_back(d));
	if(L<=mid)add(ls,l,mid,L,R,d);
	if(R>mid)add(rs,mid+1,r,L,R,d);
}

inline int find(int x)
{
	return x==fa[x]?x:find(fa[x]);
}

inline void dfs(int x,int l,int r)
{
	int renum=num,p=tot;
	for(int i=0;i<edge[x].size();i++)
	{
		int u=edge[x][i].u,v=edge[x][i].v;
		u=find(u),v=find(v);
		if(u==v)continue;
		if(siz[u]>siz[v])swap(u,v);
		k[++tot]=(wty){u,v};
		num-=(siz[u]&1)+(siz[v]&1);
		siz[v]+=siz[u];fa[u]=v;
		num+=(siz[v]&1);
	}
	if(l==r)
	{
		while(num&&pos<=m)
		{
			if(e[pos].tim<=l)
			{
				int u=e[pos].u,v=e[pos].v;
				if(e[pos].tim!=l)
				add(1,1,m,e[pos].tim,l-1,(wty){u,v});
				u=find(u),v=find(v);
				if(siz[u]>siz[v])swap(u,v);
				if(u==v){++pos;continue;}
				k[++tot]=(wty){u,v};
				num-=(siz[u]&1)+(siz[v]&1);
				siz[v]+=siz[u];fa[u]=v;
				num+=(siz[v]&1);
			}
			pos++;
		}
		ans[l]=num?-1:e[pos-1].w;
		if(ans[l]==-1)
		{
			for(int i=1;i<=l;i++)puts("-1");
			for(int i=l+1;i<=m;i++)printf("%ld\n",ans[i]);
			exit(0);
		}
	}
	else dfs(rs,mid+1,r),dfs(ls,l,mid);
	while(tot>p)
	{
		int u=k[tot].u,v=k[tot].v;
		siz[v]-=siz[u];fa[u]=u;
		tot--;
	}
	num=renum;
}

char ch,B0[1<<15],*S=B0,*T=B0;
#define getc() (S==T&&(T=(S=B0)+fread(B0,1,1<<15,stdin),S==T)?0:*S++)
int aa;inline int read(){
	while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
	while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}

main()
{
	n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		e[i].u=read(),e[i].v=read(),e[i].w=read();
		e[i].tim=i;
	}
	sort(e+1,e+1+m);num=n;
	for(int i=1;i<=n;i++)siz[i]=1,fa[i]=i;
	dfs(1,1,m);
	for(int i=1;i<=m;i++)printf("%ld\n",ans[i]);
}