自动搬运

查看原文

来自洛谷，原作者为

	yzy_rick 这个简介啊，它会自己长出来

搬运于2025-08-24 22:38:47，当前版本为作者最后更新于2023-10-09 21:43:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先我们知道，一个括号序列合法当且仅当将所有的 ( 当成 $+1$ ,将所有的 ) 当成 $-1$ ,对于任意位置的前缀和都非负，且最后一个位置的前缀和为 $0$.

那么，如果 $n$ 是奇数，直接无解。

接下来，让我们先考虑一些特殊情况；

• 如果 $s_{a_i}$ 是 ( 且 $s_{b_i}$ 是 (，那么显然是要选择 $s_{a_i}$；

• 如果 $s_{a_i}$ 是 ) 且 $s_{b_i}$ 是 )，那么显然是要选择 $s_{b_i}$。

• 如果 $s_{a_i} \not= s_{b_i}$，此时无论是直接选择 $s_{a_i}$ 还是 $a_{b_i}$ 都是不对的，反例：

  

那么考虑带悔贪心。

然而，我们会发现一个问题，这个题没有办法像一些带悔贪心的题一样建出来费用流模型，所以无法直接贪心模拟费用流。

于是我们需要建立一个反悔贪心机制，这个机制的核心点在于：对于所有的 () 和 )(，都先贪心地选择 )，然后贪心地将一些 ) 反悔成 (。

那么考虑如何利用带悔贪心将序列变为合法的。

先考虑一下，如果将一个 ) 变为 ( 对整个前缀和序列的贡献是什么？

不妨设第 $i$ 对的两个位置靠左的为 $l_i$，靠右的为 $r_i$。

那么，对于一个位置来说，无论是删去一个 )，还是加上一个(，对这个位置以及以后所有的前缀和贡献都是 $+1$。

所以把第 $i$ 对的 ) 变为 ( 的贡献就是：

对于每一个 $l_i \leq j \leq n$，$sum_j$ 会增加 $1$。

对于每一个 $r_i \leq j \leq n$，$sum_j$ 还会额外增加 $1$。

整理一下，就是：

对于每一个 $l_i \leq j < r_i$，$sum_j$ 会增加 $1$。

对于每一个 $r_i \leq j \leq n$，$sum_j$ 会增加 $2$。

但是此时又会产生一个问题：如果面对多个可以反悔的括号对，到底反悔哪个更优？

先说答案：优先选择 $r_i$ 更小的反悔。

不妨设当前的位置为 $p$，那么我们只要证明对于剩余任意一对可以反悔的 $l_j,r_j$ ,反悔第 $j$ 对不会优于第 $i$ 对就可以了。

• $r_i<r_j<p$：由于此时 $p$ 之前的位置都已经合法了，而这两个区间对于 $p$ 后面的贡献都一样，选哪个都无所谓；
• $r_i<p<r_j$：那么对于任意的 $p<x<r_j$，选择 $i$ 之后 $sum_x$ 会增加 $2$，而选择 $j$ 只能给这一段 $+1$。而且，如果 $p$ 后面有一些(( 且 $s_{r_j}$ = )，如果不反悔 $j$ 的话它还可以与后面产生贡献。综合来说，选择 $i$ 各方面还是更优的；
• $p<r_i<r_j$：与第二种情况同理。

所以，直接按照这个策略做带悔贪心就可以了。

无解的情况就是：在一个位置前缀和无论如何都 $<0$，或者最终前缀和只能 $>0$。

最后附上代码：

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pa pair<int,int>
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void file()
{
	string file_name="data";
	freopen((file_name+".in").c_str(),"r",stdin);
	freopen((file_name+".out").c_str(),"w",stdout);
}
const int N=1e5+10;
int n;
char s[2*N];
pa a[N];
//a表示一堆匹配的两个位置
int p[2*N],f[2*N];
//p表示当前位置在匹配中的另一个位置
//f表示当前位置选或者不选，f[i]=1代表选，f[i]=-1代表不选
bool solve()
{
    if(n&1)return 0;//n是奇数直接判掉
    priority_queue<int,vector<int>,greater<int>>q;
    int sum=0;
    for(int i=1;i<=2*n;i++)
    {
        if(f[i]==1){if(s[i]=='(')sum++;else sum--;}//这个位置已经标记必选
        if(s[i]!=s[p[i]]&&i<p[i])q.push(p[i]);//将r[i]加入队列中
        while(sum<0&&q.size())
        {
            int k=q.top();
            q.pop();
            f[k]=-f[k];
            f[p[k]]=-f[p[k]];
            //将这对匹配取反
            if(k<=i)sum++;
            if(p[k]<=i)sum++;
            //计算到当前位置的贡献，如果反悔的某个位置在当前位置后面，那么这个贡献到后面再算
        }
        if(sum<0)return 0;
        //当前位置前缀和无法做到>=0
    }
    if(sum!=0)return 0;
    //整个序列前缀和!=0
    return 1;
}
signed main()
{
	// file();
	int aqx=read();
	while(aqx--)
	{
		n=read();
		scanf("%s",s+1);
        //读入
        memset(p,0,sizeof(int)*(2*n+10));
        memset(f,-1,sizeof(int)*(2*n+10));
        //多测不能直接无脑memset
		for(int i=1;i<=n;i++)
        {
            int x=read(),y=read();
            a[i]=mp(x,y);
            p[x]=y,p[y]=x;
            if(s[x]==s[y])
            {
                //相同的情况，（取左边，）取后边
                if(s[x]=='(')f[x]=1;
                else f[y]=1;
            }
            else
            {
                //不相同，优先取）
                if(s[x]==')')f[x]=1;
                else f[y]=1;
            }
        }
        if(!solve())puts("-1");//无解
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(f[a[i].fi]==1)printf("0 ");
                else printf("1 ");
            }
            printf("\n");
        }
	}
	return 0;
}