题解：P10572 [JRKSJ R8] +1-1

· · 题解

题目大意

给定一个带点权的无向图，点权为括号，多次询问是否存在 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;
}