Codeforces Round 877 (Div. 2)

Bracket Walk

算法本质

思维、数据结构

题目大意

给定一个括号串s，现在存在m个询问：

• 每次询问会给出一个下标p，使得s[p]的括号反转（继承不消除影响）
• 然后询问，玩家从s头走到尾，走过的路程组成新括号串t，能否有方式使得t合法

n m <= 2e5

思路推演 - 朴素模拟

先思路，对于固定的s，如何情况才能有解：

• 显然，s长度是奇数时不可能有解。

然后发现，当多个相同的字符出现时，其数目可以视作增加任意偶数。例如(()))的字符串就可以视作还剩余奇数个(。

• 随后可以发现，对于第一次出现的多个)之前，必须存在多个(来使其合法
• 同理，最后一次出现的多个(之后，必须存在多个)使其合法
• 首尾特判一下

上述的规律相对容易好找，而且因为保证了长度是偶数，所以不会存在剩余奇数个(或)的情况。

这里麻烦的地方在于需要维护的东西：

• 连续出现的(位置
• 连续出现的)位置

为了维护以上东西并且支持动态修改，又必须得维护单个括号的位置——常用set维护某个字符的区间范围，辅助函数保证其增加（包括融合）、减少。
在这个基础上，再维护连续出现的字符位置。

整体难度不大，相当于模拟题了，需要思路清晰。

思路推演 - 巧取核心

这个思路由作者提供，没有什么思路过程，但是解题方法还算巧妙

维护连续出现的(和)，核心其实仅需第一次出现(和)的位置，还有最后一次出现的位置。
通过观察可以发现，如果不存在连续相同字符，则(一定出现在奇数下标、)出现在偶数下标，我们可以定义如何位置是合法，反之是违法。

连续相同字符必然存在违法行为（首尾也顺便特判了），我们只需要检查第一个违法行为是(还是)、最后一个违法行为是(还是)即可。
同时，因为反转操作也十分容易维护——消除违法或者新增违法即可。

ac核心代码 - 朴素模拟

笔者这里都使用的set维护，也有方法使用线段树来维护的。

头文件、宏定义、快读模板、常见变量、常见变量等略。
set<pair<int, int>> st[2];        // st[0]表示(所占的区间
set<int> cod[2];            // cod[0]表示连续(所占的区间，只存左端点即可
void jia(int l, int r, int id)        // 向cod[id]加入区间[l,r]
{
    if (r-l+1 <= 1)        return;
    cod[id].insert(l);
}
void diu(int l, int id)            // cod[id]删除以l为左端点的区间
{
    cod[id].erase(l);
}
void add(int l, int r, int id)        // 向st[id]加入[l,r]的区间
{
    if (l>r)        return;
    jia(l, r, id);
    st[id].insert({l, r});        // 每个st[id]的insert，必须伴随jia()函数
    auto it = st[id].lower_bound({l,r});
    if (it!=st[id].begin() && prev(it)->second==l-1)        // 检查能否和左边区间合并
    {
        l = prev(it)->first;
        diu(prev(it)->first, id);
        st[id].erase(prev(it));
    }
    if (next(it)!=st[id].end() && next(it)->first==r+1)        // 检查能否与右边区间合并
    {
        r = next(it)->second;
        diu(next(it)->first, id);
        st[id].erase(next(it));
    }
    diu(it->first, id);
    st[id].erase(it);
    jia(l, r, id);
    st[id].insert({l,r});
}
void del(int x, int id)
{
    auto it = st[id].upper_bound({x, 1e9});        
    if (it==st[id].begin())        return;
    it = prev(it);        // 找到x所在的区间
    auto [l, r] = *it;
    if (r<x)    return;
    diu(it->first, id);        // 分裂
    st[id].erase(it);
    add(l, x-1, id);
    add(x+1, r, id);
}
inline void solve()
{
    string s;
    cin>>n>>m>>s;
    for (int i=0; i<n; i++)
    {
        if (s[i]=='(')    add(i, i, 0);
        else            add(i, i, 1);
    }
    while (m--)
    {
        int p=in();    
        p--;        // 0下标
        if (s[p]=='(')
        {
            s[p] = ')';
            del(p, 0);
            add(p, p, 1);
        }
        else
        {
            s[p] = '(';
            del(p, 1);
            add(p, p, 0);
        }
        
        flag = 1;
        if (s[0]==')' || s[n-1]=='(')        // 首尾特判
            flag = 0;
        if (n%2==1)            // 长度奇数特判
            flag = 0;
        // 第一个连续)前方必须有连续的(守护
        if (cod[1].size() && (cod[0].size()==0 || (*cod[1].begin()) < (*cod[0].begin()) ))
             flag = 0;
        // 最后一个连续的(后方必须有连续的)守护
        if (cod[0].size() && (cod[1].size()==0 || (*cod[0].rbegin()) > (*cod[1].rbegin()) ))
            flag = 0;
        cout<<(flag ? "YES" : "NO")<<endl;
    }

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。