[LOJ2865] P4899 [IOI2018] werewolf 狼人

• 2020 年 5 月 3 日
• 筆記
• 圖論-kruskal重構樹, 數據結構-主席樹, 題解-洛谷

P4899 [IOI2018] werewolf 狼人
LOJ#2865.「IOI2018」狼人，第一次AC交互題

kruskal 重構樹+主席樹
其實知道重構樹的演算法的話，難度就主要在主席樹上

習慣從 \(1\) 開始標號，所以以下講解中的標號都是從 \(1\) 開始的
從 \(s\) 開始走，只走點 \(L,L+1,\cdots,n\)，能走到的點集記為 \(V_1\)
從 \(e\) 開始，只走 \(1,2,\cdots,R\)，能走到的點集記為 \(V_2\)
則，若 \(V_1\cap V_2 \neq \varnothing\)，就說明有解，我們可以在交集內的任意一個點變換人狼形式

第一步，求 \(V_1,V_2\)
考慮 kruskal 重構樹，先去這裡看更詳細的講解 不知道詳細不詳細，在這裡不會重頭開始講重構樹內容
建立兩個重構樹

• \(A\) 為以 \(\max(u,v)\) 為權值，用 最小 生成樹重構，可以知道，\(u,v\) 兩點路徑中，經過的點的最大編號的最小值，就是得出的重構樹中 \(lca(u,v)\) 的點權
• \(B\) 為以 \(\min(u,v)\) 為權值，用 最大 生成樹重構，可以知道，\(u,v\) 兩點路徑中，經過的點的最小編號的最大值，就是得出的重構樹中 \(lca(u,v)\) 的點權

所以，由於 kruskal 重構樹的一般性質，也可以知道，以 \(A\) 樹為例，與一個點 \(u\) 之間的路徑，經過的點的最大編號的最小值小於等於 \(x\) 的節點，就是以 從 \(u\) 到根的路徑中，深度最小的，權值小於等於 \(x\) 的那個點 為根，的子樹中的所有葉子節點
好繞，可以用來練習句子成分的確定
然後 \(x=R\) 時，這樣得到的點集，就是 \(V_2\)
同理，可以用 \(B\) 樹，以相似的方法求出 \(V_1\)

第二步，求 \(V_1,V_2\) 是否交集不為空
用主席樹，其實可以離線用樹狀數組，但是並沒有看懂是怎麼做

主席樹其實可以理解為線段樹的前綴和，我們把這些點（\(2n-1\) 個），按照在 \(A\) 樹中的 dfs 序來排序，並以這些點在 \(B\) 樹上的 dfs 序建主席樹
然後我們設通過重構樹找到的兩個點（子樹的根）分別是 \(a,b\)，那麼又因為在一個子樹內，dfs 序是連續的，所以每次查詢 \(dfn_b\cdots dfn_b+size_b-1\) 中，有沒有數在 \(dfn_a\cdots dfn_a+size_a-1\) 中
其實也不難

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
	register int x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
	return y?x:-x;
}
#define N 400006
#define M 400006
int n,m;
struct edge{
	int u,v;
}e[M];
inline int get_max(int x,int y){return x>y?x:y;}
inline int get_min(int x,int y){return x<y?x:y;}
struct TREE{
	int up[N*2],vertex;
	int son[2][N];
	int fa[19][N],size[N],dfn[N],dfscnt;
	int val[N];
	inline int find(int k){
		return k==up[k]?k:up[k]=find(up[k]);
	}
	static inline int cmp_A(edge aa,edge aaa){return get_max(aa.u,aa.v)<get_max(aaa.u,aaa.v);}
	static inline int cmp_B(edge aa,edge aaa){return get_min(aa.u,aa.v)>get_min(aaa.u,aaa.v);}
	inline void build_A(){
		std::sort(e+1,e+1+m,cmp_A);
		vertex=n;
		for(reg int i=1;i<=2*n;i++) up[i]=i;
		for(reg int u,v,i=1,cnt=1;cnt<n;i++){
			u=find(e[i].u);v=find(e[i].v);
			if(u==v) continue;
			val[++vertex]=get_max(e[i].u,e[i].v);
			son[0][vertex]=u;son[1][vertex]=v;
			cnt++;up[u]=up[v]=vertex;
		}
	}
	inline void build_B(){
		std::sort(e+1,e+1+m,cmp_B);
		vertex=n;
		for(reg int i=1;i<=2*n;i++) up[i]=i;
		for(reg int u,v,i=1,cnt=1;cnt<n;i++){
			u=find(e[i].u);v=find(e[i].v);
			if(u==v) continue;
			val[++vertex]=get_min(e[i].u,e[i].v);
			son[0][vertex]=u;son[1][vertex]=v;
			cnt++;up[u]=up[v]=vertex;
		}
	}
	void dfs(int u,int father){
		fa[0][u]=father;size[u]=1;dfn[u]=++dfscnt;
		for(reg int i=1;i<19;i++) fa[i][u]=fa[i-1][fa[i-1][u]];
		if(!son[0][u]) return;
		dfs(son[0][u],u);dfs(son[1][u],u);
		size[u]+=size[son[0][u]]+size[son[1][u]];
	}
	inline int get_A(int u,int x){
		for(reg int i=18;~i;i--)if(val[fa[i][u]]<=x) u=fa[i][u];
		return u;
	}
	inline int get_B(int u,int x){
		for(reg int i=18;~i;i--)if(val[fa[i][u]]>=x) u=fa[i][u];
		return u;
	}
}A,B;
//主席樹部分 
struct tr{
	tr *ls,*rs;
	int x;
}dizhi[10000006],*root[N];
int tot;
inline int cmp(int x,int y){return A.dfn[x]<A.dfn[y];}
void build(tr *tree,int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	tree->ls=&dizhi[tot++];tree->rs=&dizhi[tot++];
	build(tree->ls,l,mid);build(tree->rs,mid+1,r);
}
void insert(tr *last,tr *tree,int l,int r,int num,int k){
	if(l==r) return tree->x=last->x+k,void();
	int mid=(l+r)>>1;
	*tree=*last;
	if(num<=mid){
		tree->ls=&dizhi[tot++];
		insert(last->ls,tree->ls,l,mid,num,k);
	}
	else{
		tree->rs=&dizhi[tot++];
		insert(last->rs,tree->rs,mid+1,r,num,k);
	}
	tree->x=tree->ls->x+tree->rs->x;
}
int find(tr *left,tr *right,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return right->x-left->x;
	int mid=(l+r)>>1;
	if(ql<=mid){
		if(find(left->ls,right->ls,l,mid,ql,qr)) return 1;
	}
	if(qr>mid){
		if(find(left->rs,right->rs,mid+1,r,ql,qr)) return 1;
	}
	return 0;
}
int main(){
	n=read();m=read();int q=read();
	for(reg int i=1;i<=m;i++){
		e[i].u=read()+1;e[i].v=read()+1;
	}
	A.build_A();B.build_B();
	A.dfs(2*n-1,2*n-1);B.dfs(2*n-1,2*n-1);
	int tmp[n*2];
	for(reg int i=1;i<n*2;i++) tmp[i]=i;
	std::sort(tmp+1,tmp+n*2,cmp);
	for(reg int i=0;i<2*n;i++) root[i]=&dizhi[tot++];
	build(root[0],1,2*n-1);
	for(reg int i=1;i<2*n;i++) insert(root[i-1],root[i],1,2*n-1,B.dfn[tmp[i]],tmp[i]<=n);
	reg int s,t,L,R;
	while(q--){
		s=read()+1;t=read()+1;L=read()+1;R=read()+1;
		//從 s 開始，能走 L 到 n，最小值不小於 L，用 B 樹
		//從 t 開始，能走 1 到 R，最大值不大於 R，用 A 樹
		//找交集
		int tmpa=A.get_A(t,R),tmpb=B.get_B(s,L);
		std::puts(find(root[A.dfn[tmpa]-1],root[A.dfn[tmpa]+A.size[tmpa]-1],1,2*n-1,B.dfn[tmpb],B.dfn[tmpb]+B.size[tmpb]-1)?"1":"0");
	}
	return 0;
}