Cf603e pastoral oddities [CDQ divide and conquer, revocable and search set]

On the subject

Topic link :https://www.luogu.com.cn/problem/CF603E

---

The main idea of the topic

There was... At the beginning $n$ A little bit , There is no side .

Add in sequence $m$ Edge of strip weight , After each addition, ask whether there is an edge set , The degree satisfying each point is odd , Seek to minimize the maximum weight of this edge set .

$1\le n\le 10^5,1\le m\le 3\times 10^5$

---

Their thinking

First, consider the condition for the existence of this edge set , It can be proved that there is an edge set satisfying the condition if and only if the size of the connected blocks is even .
The need for ： For a connection block , Because each edge contributes an even number of degrees , And if this connected block is an odd number of points , Then if the total legal degree is Odd number × Odd number = Odd number , Obviously, it can't be even , So there is no such situation .
adequacy ： If there is a point whose degree is odd , Then the degree of at least one point in the Unicom fast is odd , We can adjust to the legal situation by deleting the edge on the path of these two points on the way .

And it is definitely the best if we can connect the edges , Because there is no edge connection, the number of odd connected blocks will increase .

Then consider using CDQ Divide and conquer to solve this problem , Notice that the answer must be monotonous , Our process is to record the current interval $[l,r]$ Answer range of $\{L,R\}$.

First calculate $an{s}_{mid}$, Then at this time we can be divided into $[l,mid-1]\{an{s}_{mid},R\}$ and $[mid+1,r]\{L,an{s}_{mid}\}$

At this time, the two intervals are separated , This suggests that the violent enumeration of these intervals is the complexity of normal partition .

Then it's obvious , We calculated $an{s}_{mid}$ After the left and right sides of recursive processing , With revocable and search set processing .

Time complexity ：$O(m\log m\log n)$

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e5+10;
struct node{
    
	int x,y,w,id;
}a[N],b[N];
struct clnode{
    
	int x,y,siz,dep;
}cl[N];
int n,m,sum,clt,fa[N],siz[N],dep[N];
int ans[N],rk[N];
int find(int x)
{
    return (fa[x]==x)?x:find(fa[x]);}
void unionn(int x,int y){
    
	x=find(x);y=find(y);
	if(x==y)return;
	if(dep[x]>dep[y])swap(x,y);
	cl[++clt]=(clnode){
    x,y,siz[y],dep[y]};
	sum-=(siz[x]&1)&(siz[y]&1);
	fa[x]=y;siz[y]+=siz[x];
	dep[y]=max(dep[y],dep[x]+1);
}
void clearto(int d){
    
	while(clt>d){
    
		int x=cl[clt].x,y=cl[clt].y;
		siz[y]=cl[clt].siz;
		dep[y]=cl[clt].dep;
		sum+=(siz[x]&1)&(siz[y]&1);
		fa[x]=x;clt--;
	}
	return;
}
void cdq(int l,int r,int L,int R){
    
	if(l>r)return;
	int mid=(l+r)>>1,now=clt;
	for(int i=l;i<=mid;i++)
		if(rk[i]<L)unionn(a[i].x,a[i].y);
	int mow=clt;
	for(int i=L;i<=R;i++){
    
		if(b[i].id<=mid)unionn(b[i].x,b[i].y);
		if(!sum){
    ans[mid]=i;break;}
	}
	if(!ans[mid]){
    
		clearto(mow);
		cdq(mid+1,r,L,R);
		return;
	}
	clearto(mow);
	cdq(mid+1,r,L,ans[mid]);
	clearto(now);
	for(int i=L;i<ans[mid];i++)
		if(b[i].id<l)unionn(b[i].x,b[i].y);
	cdq(l,mid-1,ans[mid],R);
	clearto(now);return;
}
bool cmp(node x,node y)
{
    return x.w<y.w;}
int main()
{
    
	scanf("%d%d",&n,&m);sum=n/2;
	if(n&1){
    
		for(int i=1;i<=m;i++)
			puts("-1");
		return 0;
	}
	for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;
	for(int i=1;i<=m;i++){
    
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
		a[i].id=i;b[i]=a[i];
	}
	sort(b+1,b+1+m,cmp);
	for(int i=1;i<=m;i++)rk[b[i].id]=i;
	cdq(1,m,1,m);
	for(int i=1;i<=m;i++)
		if(!ans[i])puts("-1");
		else printf("%d\n",b[ans[i]].w);
	return 0;
}