[Luogu4899][IOI2018] werewolf 狼人

luogu

sol

\(\mbox{IOI2018}\)的出题人有没有看过\(\mbox{NOI2018}\)的题目呀。。。

\(\mbox{Kruskal}\)重构树+二维数点。

题目相当于是问你从\(S\)出发只经过\(\ge L\)的点，和从\(T\)出发只经过\(\le R\)的点有没有交集。

分别建两棵最大/最小\(\mbox{Kruskal}\)重构树，这样从\(S\)出发，从\(T\)出发能到达的点就分别是两棵树上的一个子树。以点在两棵树上的\(dfs\)序作为两维坐标，每次询问就是问你某个矩形区域里面有没有点。

code

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 4e5+5;

struct president_tree{int ls,rs,sz;}t[N*35];

int n,m,q,val[N],rt[N],tot;

vector<int>E[N];

struct Kruskal_rebuild_tree{

	int ty;

	int fa[N],nxt[N],hd[N],pa[20][N],dfn[N],low[N],tim;

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

	void dfs(int u){

		dfn[u]=++tim;

		for (int j=1;j<20;++j) pa[j][u]=pa[j-1][pa[j-1][u]];

		for (int v=hd[u];v;v=nxt[v]) dfs(v);

		low[u]=tim;

	}

	void work(){

		for (int i=1;i<=n;++i) fa[i]=i;

		if (ty){

			for (int u=n;u;--u)

			for (int v:E[u])

				if (u<v){

					v=find(v);if (u==v) continue;

					nxt[v]=hd[u],hd[u]=v,fa[v]=pa[0][v]=u;

				}

			dfs(1);

		}else{

			for (int u=1;u<=n;++u)

			for (int v:E[u])

				if (u>v){

					v=find(v);if (u==v) continue;

					nxt[v]=hd[u],hd[u]=v,fa[v]=pa[0][v]=u;

				}

			dfs(n);

		}

	}

	int jump(int u,int k){

		for (int j=19;~j;--j)

			if (pa[j][u]&&((ty&&pa[j][u]>=k)||(!ty&&pa[j][u]<=k)))

				u=pa[j][u];

		return u;

	}

}A,B;

void modify(int &x,int l,int r,int p){

	t[++tot]=t[x];++t[x=tot].sz;

	if (l==r) return;int mid=l+r>>1;

	if (p<=mid) modify(t[x].ls,l,mid,p);

	else modify(t[x].rs,mid+1,r,p);

}

int query(int x,int y,int l,int r,int ql,int qr){

	if (l>=ql&&r<=qr) return t[x].sz-t[y].sz;

	int mid=l+r>>1,s=0;

	if (ql<=mid) s+=query(t[x].ls,t[y].ls,l,mid,ql,qr);

	if (qr>mid) s+=query(t[x].rs,t[y].rs,mid+1,r,ql,qr);

	return s;

}

int main(){

	n=gi();m=gi();q=gi();

	for (int i=1;i<=m;++i){

		int u=gi()+1,v=gi()+1;

		E[u].push_back(v);E[v].push_back(u);

	}

	A.ty=1;A.work();B.work();

	for (int i=1;i<=n;++i) val[A.dfn[i]]=B.dfn[i];

	for (int i=1;i<=n;++i) modify(rt[i]=rt[i-1],1,n,val[i]);

	while (q--){

		int s=gi()+1,e=gi()+1,l=gi()+1,r=gi()+1;

		s=A.jump(s,l);e=B.jump(e,r);

		puts(query(rt[A.low[s]],rt[A.dfn[s]-1],1,n,B.dfn[e],B.low[e])?"1":"0");

	}

	return 0;

}