自动搬运

查看原文

来自洛谷，原作者为

	未来姚班zyl 欢迎加入粉丝团！https://www.luogu.com.cn/team/72518|AFO

搬运于2025-08-24 22:59:17，当前版本为作者最后更新于2024-06-08 19:36:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定一个带点权的无向图，点权为括号，多次询问是否存在 $x\rightarrow y$ 的路径（可以不是简单路径），使得路径上的点权构成合法的括号序列。

题目分析

这道题如果从做完的角度来看是非常简单的，但是从分析的过程来看，每一步都是要非常强大的基本功的。

考虑合法的路径满足的性质：

• 长度一定得是偶数。

这个限制只需要将每个点拆成奇点和偶点即可，然后查询变为 $x$ 的奇点到 $y$ 的偶点是否存在合法路径。之后的分析我们就可以不用考虑奇偶性。

显然，如果有一条边连接了两个相同的括号，我们就可以无限复制这个括号，称这样的边为 $)$ 边或者 $($ 边，统称括号边。我们先考虑没有括号边的情况。

则路径都形如 $()()()\dots$。这是比较极限的，必须相邻的括号两两匹配。

这样我们可以发现，对于括号边带来的括号，是不可能用上面这些括号匹配的，只能括号边之间两两匹配。由于可以无限复制，我们只需要第一次出现的括号边是 $($ 边，最后一次出现的括号边是 $)$ 边即可平衡，否则就非法。

这时候来考虑是否存在合法路径，首先两个点得在同一个连通块里。

• 没有括号边

则我们拿非括号边跑并查集即可。

• 有括号边

则需要从一个起点不经过 $)$ 边走到一个 $($ 边，然后走到一个 $)$ 括号边，并不经过 $($ 边走到终点。我们只需要记录每个并查集是否可以直接到达这两类边即可。

复杂度 $O(n\log n)$，直接搜索来处理连通性可以 $O(n)$，但比赛的时候肯定是写并查集更方便！

#include<bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define pc putchar
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
using namespace std;
const int N =1e6+5,M=2e6+5;
int n,m,q,h[N],to[M],nxt[M],cnt,a[N],f[N],fa[N];
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
inline int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
bool C[N],D[N],Spe[N];
string s;
inline void add_(int a,int b){
	s[a]!=s[b]?fa[Find(a)]=Find(b):Spe[a]=Spe[b]=1,f[find(a)]=find(b),to[++cnt]=b,nxt[cnt]=h[a],h[a]=cnt;
}
int main(){
	n=read(),m=read(),q=read();
	cin>>s,s='#'+s+s;
	rep(i,1,n<<1)f[i]=fa[i]=i;
	while(m--){
		int x=read(),y=read();
		add_(x,y+n),add_(y+n,x),add_(y,x+n),add_(x+n,y);
	}
	rep(x,1,n<<1){
		int X=Find(x);
		e(x)C[X]|=s[y]=='('&&Spe[y],D[X]|=s[y]==')'&&Spe[y];
	}
	while(q--){
		int x=read(),y=read();
		if(s[x]==')'||s[y]=='('){
			pc('0');
			continue;
		}
		if(find(x)!=find(y+n)){
			pc('0');
			continue;
		}
		pc(C[Find(x)]&&D[Find(y+n)]?'1':Find(x)==Find(y+n)?'1':'0');
	}
	return 0;
}