YetAnotherBracketSequence

Each input file only contains one test case.
The first line contains two integers n and m (1 ≤ n, m ≤ $10^5$ ), indicating the length of the given Bracket Sequence and the times of Onlystar change the Bracket Sequence.
The second line contains a string S and its length is n, indicating the given Bracket Sequence.
Then, the following m lines, each line contains a integer x (1 ≤ x ≤ n), indicating the position that Onlystar will change the Bracket Sequence, it means '(' will replace to ')' and ')' will replace to '('.

C++11(clang++ 3.9) 解法, 执行用时: 249ms, 内存消耗: 3536K, 提交时间: 2020-06-03 20:38:30

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+1;
char str[maxn];
int sum[4*maxn], mi[4*maxn];

void modify(int o, int x, int l, int r, int lr) {
	if (l == r) {
		sum[o] = mi[o] = x;
		return ;
	}
	int mid = l + r >> 1;
	if (mid >= lr) modify(o<<1,x,l,mid,lr);
	else modify(o<<1|1,x,mid+1,r,lr);
	sum[o] = sum[o<<1] + sum[o<<1|1];
	mi[o] = min(mi[o<<1], sum[o<<1] + mi[o<<1|1]); 
}

int main() {
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; ++ i) {
		cin >> str[i];
		if (str[i] == '(') modify(1,1,1,n,i);
		else modify(1,-1,1,n,i);
	}
	while(m--) {
		int d;
		cin >> d;
		if (str[d] == '(') str[d] = ')', modify(1,-1,1,n,d);
		else str[d] = '(', modify(1,1,1,n,d);
		// cout << sum[1] << " " << mi[1] << endl;
		if (sum[1] == 0 && mi[1] >= 0) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 290ms, 内存消耗: 3176K, 提交时间: 2020-06-05 16:25:32

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int cnt[N<<2];
int mn[N<<2];
void update(int t,int l,int r,int x,int val)
{
	if(l>=r)
	{
		cnt[t]=val;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)update(t<<1,l,mid,x,val);
	else update(t<<1|1,mid+1,r,x,val);
	cnt[t]=cnt[t<<1]+cnt[t<<1|1];
	mn[t]=min(mn[t<<1],cnt[t<<1]+mn[t<<1|1]);
}
int main()
{
	int n,m;
	cin>>n>>m;
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
    	int k=s[i]==')'?-1:1;
    	update(1,1,n,i+1,k);
	}
	while(m--)
	{
		int x;
		cin>>x;
		if(s[x-1]=='(')
		{
			update(1,1,n,x,-1);
			s[x-1]=')';
		}
		else
		{
			update(1,1,n,x,1);
			s[x-1]='(';
		}
		if(cnt[1]==0&&mn[1]>=0)cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}

详情