题解：CF1838D Bracket Walk

· · 题解

审核题解，管理员辛苦了。

点击跳转题意

先考虑一些特殊情况。

:::info[特殊情况] 第一位是右括号，最后一位是左括号（废话），长度为奇数都不合法。

详细证明一下，显然一个合法括号序长度必须是偶数，但是我们无论怎么绕多加的括号数都是偶数（来回走嘛），凑不出偶数。 :::

然后考虑重复走一大段可以拆分成反复走一小段。

那么哪些段重复走是有用的，形如 )(，()，是没有用的，只有连续右括号或连续左括号是有用的。

（下面的分讨都是在特判完特殊情况后进行的）

考虑如果根本没有连续段，一定合法。

考虑只有一种连续段，一定不合法。

考虑两种连续段都有，除非第一个是右括号连续段，最后一个是左括号连续段才能合法。

然后就考虑维护每个连续括号序，直接上 set 即可。

:::info[详细说明] 我们开两个 set 分别存储连续左括号与连续右括号。 对于每一个点，我们只考虑它与后面点的贡献。 修改时去更新这个点前后所产生的贡献，直接做即可。 :::

#include <bits/stdc++.h>
using namespace std;
int n;
set <int> s1,s2;
char a[200005];
void sqqrt(int i,int op)
{
    if(a[i]==a[i+1] && a[i]=='(')
    {
        if(op==1)
            s1.insert(i);
        else
            s1.erase(i);
    }
    if(a[i]==a[i+1] && a[i]==')')
    {
        if(op==1)
            s2.insert(i);
        else
            s2.erase(i);
    }
}
void update(int i)
{
    if(i!=1)
        sqqrt(i-1,0);
    if(i!=n)
        sqqrt(i,0);
    if(a[i]=='(')
        a[i]=')';
    else
        a[i]='(';
    if(i!=1)
        sqqrt(i-1,1);
    if(i!=n)
        sqqrt(i,1);
}
bool query()
{
    if(a[1]==')' || a[n]=='(')
        return 0;
    if(s1.empty() && s2.empty())
        return 1;
    else if(s1.empty() || s2.empty())
        return 0;
    auto i=s1.begin();
    auto j=s2.begin();
    if(*i>*j) return 0;
    i=s1.end();
    j=s2.end();
    i--,j--;
    if(*i>*j) return 0; 
    return 1;
}
signed main()
{
    int q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<n;i++)
        sqqrt(i,1);
    while(q--)
    {
        int id;
        cin>>id;
        if(n%2==1)
        {
            cout<<"NO"<<endl;
            continue;
        }
        update(id);
        if(query())
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}

看到这里，就点个赞吧。