Solution -「洛谷 P5787」「模板」二分图（线段树分治）

(mathcal{Description})

  Link.

   (n) 个结点的图，(m) 条形如 ((u,v,l,r)) 的边，表示一条连接 (u) 和 (v) 的无向边会在时间 ((l,r]) 内存在，时间范围在 ([0,K])。判断每个时刻的图是否是二分图。

  (n,Kle10^5)，(mle2 imes10^5)。

(mathcal{Solution})

  线段树分治其实和线段树没啥关系。（

  个人感觉线段树分治节约时间的方法和整体二分很像——把一些询问都需要的信息统一进行，以减少维护修改操作的次数。线段树二分是在时间轴上二分。记当前时间区间 ([l,r])，作用所有完全覆盖 ([l,r]) 的修改（它们是这个区间内的询问都需要的），然后递归左右区间，回溯时撤销当前区间的所有修改。

  对于本题，可以用 (n+n) 个虚点的并查集维护二分图——对于一条边 ((u,v))，合并 ((u,v')) 和 ((v,u'))。若 (u,v) 在同一集合，显然图上已存在奇环，当前时间区间内的所有询问全部判否，否则递归解答即可。

  复杂度 (mathcal O(nlog^2 n))。

(mathcal{Code})

/* Clearink */

#include <cstdio>
#include <vector>

inline int rint () {
	int x = 0, f = 1; char s = getchar ();
	for ( ; s < '0' || '9' < s; s = getchar () ) f = s == '-' ? -f : f;
	for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
	return x * f;
}

template<typename Tp>
inline void wint ( Tp x ) {
	if ( x < 0 ) putchar ( '-' ), x = ~ x + 1;
	if ( 9 < x ) wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

const int MAXN = 1e5, MAXM = 2e5;
int n, m, K;

struct Edge {
	int u, v, l, r;
	inline void read () { u = rint (), v = rint (), l = rint (), r = rint (); }
} tmp;
std::vector<Edge> alle;

struct DSU {
	int fa[MAXN * 2 + 5], siz[MAXN * 2 + 5];
	int top, ry[MAXM * 2 + 5], rfa[MAXM * 2 + 5], rsiz[MAXM * 2 + 5];
	inline void init () { for ( int i = 1; i <= n << 1; ++ i ) siz[fa[i] = i] = 1; }
	inline int find ( const int x ) { return x ^ fa[x] ? find ( fa[x] ) : x; }
	inline bool unite ( int x, int y ) {
		if ( ( x = find ( x ) ) == ( y = find ( y ) ) ) return false;
		if ( siz[x] < siz[y] ) x ^= y ^= x ^= y;
		++ top, ry[top] = y, rfa[top] = fa[y], rsiz[top] = siz[x];
		return siz[fa[y] = x] += siz[y], true;
	}
	inline void undo ( const int sta ) {
		for ( ; top > sta; -- top ) {
			siz[fa[ry[top]]] = rsiz[top];
			fa[ry[top]] = rfa[top];
		}
	}
} dsu;

inline void solve ( const int l, const int r, std::vector<Edge>& vec ) {
	int mid = l + r >> 1, curs = dsu.top, dis = 0;
	std::vector<Edge> vecL, vecR;
	for ( auto e: vec ) {
		if ( e.l <= l && r <= e.r ) {
			if ( dsu.find ( e.u ) == dsu.find ( e.v ) ) {
				dis = true, vecL.clear (), vecR.clear ();
				break;
			}
			dsu.unite ( e.u, e.v + n ), dsu.unite ( e.v, e.u + n );
		} else {
			if ( e.l <= mid )  vecL.push_back ( e );
			if ( mid < e.r ) vecR.push_back ( e );
		}
	}
	vec.clear ();
	if ( dis ) for ( int i = l; i <= r; ++ i ) puts ( "No" );
	else if ( l ^ r ) solve ( l, mid, vecL ), solve ( mid + 1, r, vecR );
	else puts ( "Yes" );
	dsu.undo ( curs );
}

int main () {
	n = rint (), m = rint (), K = rint ();
	for ( int i = 1; i <= m; ++ i ) {
		tmp.read (), ++ tmp.l;
		alle.push_back ( tmp );
	}
	dsu.init (), solve ( 1, K, alle );
	return 0;
}

(mathcal{Details})

  左开右开，左开右闭，左闭右开，左闭右闭……傻傻分不清qwq。