Newnode

妈呀。。。调了一个上午。。。哭瞎了。。。编程能力太弱了

题意：每条边有出现和删除时间，即时询问图是否是二分图。

这种题显然是类似于离线动态图的问题= =什么？你不知道？wc时怎么听课的？去A掉http://codeforces.com/gym/100551五题就好辣

（虽然D我并不会做）

这类题目一般有两个方法：

1. 对时间分治

2. 维护以删除时间为边权的最大生成树(推荐)

下面详(jian)细(dan)讲讲

对时间分治

额，你们都会吧，比如当前区间是[l,r]，把包含时间[l,r]的边都加入，再递归到[l,Mid],[Mid+1,r]，在这道题里用可持久化并查集来维护(很像NOIP普及组食物链？)，懂了吧，又会被卡常又会被卡内存，我并没有A掉= =，A掉的请联系我= =

时间复杂度$O\left(n \log^2 n\right)$

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;

const int N=200005;

#define Pr pair<int,int>
#define x first
#define y second
#define Mid (l+r>>1)

int fa[N*40],tag[N*40],Lc[N*40],Rc[N*40],rt[N*3],Ans[N],ta,n,m,t;
vector<Pr> E[N*3];
queue<int> Q,q[N*3];

int New()
{
	int k;
	if(!Q.empty())
		k=Q.front(),
		Q.pop();
	else
		k=++ta;
	Lc[k]=Rc[k]=fa[k]=tag[k]=0;
	return k;
}

void build(int& x,int l,int r)
{
	x=New();
	if(l==r)
		fa[x]=l;
	else
		build(Lc[x],l,Mid),
		build(Rc[x],Mid+1,r); 
}

Pr g_f(int x,int l,int r,int p)
{
	if(l==r)
		return Pr(fa[x],tag[x]);
	return p<=Mid?g_f(Lc[x],l,Mid,p):g_f(Rc[x],Mid+1,r,p);
}

void C_f(int& x,int l,int r,int p,int f,int t,int fff)
{
	int y=x;
	x=New();
	Lc[x]=Lc[y];Rc[x]=Rc[y];
	q[fff].push(x);
	if(l==r)
		fa[x]=f,tag[x]=t;
	else if(p<=Mid)
		C_f(Lc[x],l,Mid,p,f,t,fff);
	else
		C_f(Rc[x],Mid+1,r,p,f,t,fff);
}

Pr g_f(int& rt,int x,int fff)
{
	Pr fx=g_f(rt,1,n,x),fw=fx;
	int w=x,tg=fx.y;
	while(fx.x!=x)
		x=fx.x,fx=g_f(rt,1,n,x),tg^=fx.y;
	fx.y=tg;
	while(fw.x!=w)
		C_f(rt,1,n,w,fx.x,tg,fff),tg^=fw.y,w=fw.x,fw=g_f(rt,1,n,w);
	return fx;
}

bool Union(int& rt,int x,int y,int fff)
{
	Pr fx=g_f(rt,x,fff),fy=g_f(rt,y,fff);
	if(fx.x==fy.x&&fx.y==fy.y)
		return 0;
	if(fx.x!=fy.x)
		C_f(rt,1,n,fx.x,fy.x,1^fx.y^fy.y,fff);
	return 1;
}

#define lc (x<<1)
#define rc (x<<1|1)

void Ins(int x,int l,int r,int L,int R,Pr e)
{
	if(L<=l&&r<=R)
		E[x].push_back(e);
	else
	{
		if(L<=Mid)
			Ins(lc,l,Mid,L,R,e);
		if(R>Mid)
			Ins(rc,Mid+1,r,L,R,e);
	}
}

void Solve(int x,int l,int r)
{
	rt[x]=rt[x>>1];
	for(int i=0;i<E[x].size();i++)
		if(!Union(rt[x],E[x][i].x,E[x][i].y,x))
		{
			while(!q[x].empty())
				Q.push(q[x].front()),q[x].pop();
			return;
		}
	if(l==r)
		Ans[l]=1;
	else
		Solve(lc,l,Mid),
		Solve(rc,Mid+1,r);
	while(!q[x].empty())
		Q.push(q[x].front()),q[x].pop();
}

int main()
{
	scanf("%d%d%d",&n,&m,&t);
	build(rt[0],1,n);
	for(int i=1,u,v,l,r;i<=m;i++)
	{
		scanf("%d%d%d%d",&u,&v,&l,&r);
		if(l!=r)
			Ins(1,1,t,l+1,r,Pr(u,v));
	}
	Solve(1,1,t);
	for(int i=1;i<=t;i++)
		if(Ans[i])
			puts("Yes");
		else
			puts("No");
	return 0;
}

维护以删除时间为边权的最大生成树

这个呢，是xyz主要讲的方法辣，显然删除的时候不需要考虑其他边，非常方便，只要维护奇数环上的最小边权的最大值就好= =

又好写又快= =跪qoqoppp。。。

时间复杂度$O\left(n \log n\right)$

#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <vector>
#include    <deque>
#include    <queue>
#include      <set>
#include      <map>
using namespace std;

const int N=400005;

typedef long long LL;

struct EDGE
{
	int u,v,val,id;
}e[N];

int n,m,t,tot,r[N],p[N],c[N][2],v[N],M[N],sz[N],tag[N],MAXALL;

vector<int> Ins[N],Del[N];

#define Lc c[x][0]
#define Rc c[x][1]

bool ir(int x)
{
	return x&&(!p[x]||(c[p[x]][0]!=x&&c[p[x]][1]!=x));
}

void pd(int x)
{
	if(r[x])
		r[Lc]^=1,r[Rc]^=1,swap(Lc,Rc),r[x]=0;
}

void pu(int x)
{
	M[x]=x;
	if(Lc&&v[M[Lc]]<v[M[x]])
		M[x]=M[Lc];
	if(Rc&&v[M[Rc]]<v[M[x]])
		M[x]=M[Rc];
	sz[x]=sz[Lc]+sz[Rc]+1;
}

void apd(int x)
{
	if(!ir(x))
		apd(p[x]);
	pd(x);
}

void Rot(int x)
{
	int y=p[x],w=ir(y),k=c[y][1]==x;
	p[c[y][k]=c[x][!k]]=y;c[x][!k]=y;
	p[x]=p[y];p[y]=x;
	if(!w)
	 	c[p[x]][c[p[x]][1]==y]=x;
	pu(y);
}

void sp(int x)
{
	apd(x);
	while(!ir(x))
		if(ir(p[x]))
			Rot(x);
		else if((c[p[x]][0]==x)==(c[p[p[x]]][0]==p[x]))
			Rot(p[x]),Rot(x);
		else
			Rot(x),Rot(x);
	pu(x);
}

int Ac(int x)
{
	int y=0;
	for(;x;x=p[x])
	 	sp(x),Rc=y,pu(y=x);
	return y;
}

void Mr(int x)
{
	r[Ac(x)]^=1;sp(x);
}
int fr(int x)
{
	Ac(x);sp(x);
	for(pd(x);Lc;pd(x=Lc));
	return x;
}

void lk(int x,int y)
{
	if(fr(x)==fr(y))
		return;
	Mr(y);Ac(y);sp(y);p[y]=x;
}

#undef Lc
#undef Rc

int main()
{
	scanf("%d%d%d",&n,&m,&t);
	tot=n;
	for(int i=1;i<=n;i++)
		v[i]=1<<30;
	for(int i=1,l;i<=m;i++)
	{
		scanf("%d%d%d%d",&e[i].u,&e[i].v,&l,&e[i].val);
		if(l!=e[i].val)
			Ins[l+1].push_back(i),
			Del[e[i].val+1].push_back(i);
	}
	for(int i=1;i<=t;i++)
	{
		for(int j=0;j<Ins[i].size();j++)
		{
			int k=Ins[i][j],U=e[k].u,V=e[k].v;
			if(fr(U)!=fr(V))
				v[++tot]=e[k].val,
				lk(U,tot),
				lk(V,tot),
				e[k].id=tot;
			else
			{
				Mr(U);Ac(V);sp(V);
				int pos=M[V];
				sp(pos);
				if(!((sz[pos]/2)&1))
					MAXALL=max(MAXALL,min(v[pos],e[k].val));
				if(v[pos]<e[k].val)
					p[c[pos][0]]=p[c[pos][1]]=0,
					v[++tot]=e[k].val,
					lk(U,tot),
					lk(V,tot),
					e[k].id=tot;
			}
		}
		for(int j=0;j<Del[i].size();j++)
		{
			int k=Del[i][j],U=e[k].u,V=e[k].v;
			if(e[k].id)
			{
				int pos=e[k].id;
				Mr(U);Ac(V);sp(pos);
				if(c[pos][0]==U&&c[pos][1]==V)
					p[U]=0,p[V]=0;
			}
		}
		puts(MAXALL<i?"Yes":"No");
	}
	return 0;
}