Bracket Walk (Codeforces 1838D)
Tags: Greedy, strings

There is a string $$$s$$$ of length $$$n$$$ consisting of the characters '(' and ')'. You are walking on this string. You start by standing on top of the first character of $$$s$$$, and you want to make a sequence of moves such that you end on the $$$n$$$-th character. In one step, you can move one space to the left (if you are not standing on the first character), or one space to the right (if you are not standing on the last character). You may not stay in the same place, however you may visit any character, including the first and last character, any number of times.At each point in time, you write down the character you are currently standing on. We say the string is walkable if there exists some sequence of moves that take you from the first character to the last character, such that the string you write down is a regular bracket sequence.A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example, bracket sequences "()()", "(())" are regular (the resulting expressions are: "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.One possible valid walk on $$$s=\mathtt{(())()))}$$$. The red dot indicates your current position, and the red string indicates the string you have written down. Note that the red string is a regular bracket sequence at the end of the process.You are given $$$q$$$ queries. Each query flips the value of a character from '(' to ')' or vice versa. After each query, determine whether the string is walkable.Queries are cumulative, so the effects of each query carry on to future queries.

Input: The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2\cdot 10^5$$$) — the size of the string and the number of queries, respectively.The second line of the input contains a string $$$s$$$ of size $$$n$$$, consisting of the characters '(' and ')' — the initial bracket string.Each of the next $$$q$$$ lines contains a single integer $$$i$$$ ($$$1\le i \le n$$$) — the index of the character to flip for that query.

Output: For each query, print "YES" if the string is walkable after that query, and "NO" otherwise.You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Note: In the first example:   After the first query, the string is (())()()(). This string is a regular bracket sequence, so it is walkable by simply moving to the right.  After the second query, the string is (())()))(). If you move right once, then left once, then walk right until you hit the end of the string, you produce the string (((())()))(), which is a regular bracket sequence.  After the third query, the string is ()))()))(). We can show that this string is not walkable.  In the second example, the strings after the queries are ()) and ()(, neither of which are walkable.

Sample Inputs:
10 9
(())()()))
9
7
2
6
3
6
7
4
8

3 2
(()
2
3

Sample Outputs:
YES
YES
NO
NO
YES
NO
YES
NO
NO

NO
NO

Solution (Python):
import heapq

def bracket_walk(str):
    s = set()
    (min, max) = ([], [])
    for i in range(1, len(str) + 1):
        if str[i - 1] == '(' and i % 2 == 0:
            s.add(i)
            heapq.heappush(min, i)
            heapq.heappush(max, -i)
        elif str[i - 1] == ')' and i % 2 != 0:
            s.add(i)
            heapq.heappush(min, i)
            heapq.heappush(max, -i)
    return (s, min, max)
if __name__ == '__main__':
    (n, q) = list(map(int, input().split()))
    Str = input()
    (s, min, max) = bracket_walk(Str)
    for i in range(q):
        x = int(input())
        if n % 2 == 1:
            print('NO')
            continue
        if x in s:
            s.remove(x)
        else:
            s.add(x)
            heapq.heappush(min, x)
            heapq.heappush(max, -x)
        if len(s) == 0:
            print('YES')
            continue
        while min and min[0] not in s:
            heapq.heappop(min)
        while max and -max[0] not in s:
            heapq.heappop(max)
        if min[0] % 2 == 0 and -max[0] % 2 == 1:
            print('YES')
        else:
            print('NO')

Solution (Python):
import sys
import heapq
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def check(S, idx):
    return 1 if S[idx] == S[idx - 1] or S[idx] == S[idx + 1] else 0

def helper(S, idx):
    res = [-1, -1, -1]
    if S[idx] == '(' and check(S, idx):
        res[1] = 1
    elif S[idx] == ')' and check(S, idx):
        res[1] = 0
    if idx > 1:
        idx -= 1
        if S[idx] == '(' and check(S, idx):
            res[0] = 1
        elif S[idx] == ')' and check(S, idx):
            res[0] = 0
        idx += 1
    if idx < len(S) - 2:
        idx += 1
        if S[idx] == '(' and check(S, idx):
            res[2] = 1
        elif S[idx] == ')' and check(S, idx):
            res[2] = 0
        idx -= 1
    return res

def solve():
    (N, q) = map(int, input().split())
    S = list(''.join(['#', input().strip(), '#']))
    Q = [int(input()) for _ in range(q)]
    ip = [-1] * (N + 2)
    val = 0
    (hp, hn) = ([], [])
    (hp2, hn2) = ([], [])
    for i in range(1, N + 1):
        if S[i] == S[i - 1] or S[i] == S[i + 1]:
            if S[i] == '(':
                heapq.heappush(hp, i)
                heapq.heappush(hp2, -i)
                ip[i] = 1
            else:
                heapq.heappush(hn, i)
                heapq.heappush(hn2, -i)
                ip[i] = 0
        val += 1 if S[i] == '(' else -1
    for idx in Q:
        if val % 2:
            print('NO')
            continue
        val += 2 if S[idx] == ')' else -2
        res = [[], []]
        res[0] = helper(S, idx)
        S[idx] = ')' if S[idx] == '(' else '('
        res[1] = helper(S, idx)
        for i in range(3):
            if res[0][i] != res[1][i] and res[1][i] != -1:
                heapq.heappush(hp, idx - 1 + i) if res[1][i] == 1 else heapq.heappush(hn, idx - 1 + i)
                heapq.heappush(hp2, -(idx - 1 + i)) if res[1][i] == 1 else heapq.heappush(hn2, -(idx - 1 + i))
            ip[idx - 1 + i] = res[1][i]
        while hp and ip[hp[0]] != 1:
            heapq.heappop(hp)
        while hn and ip[hn[0]] != 0:
            heapq.heappop(hn)
        while hp2 and ip[-hp2[0]] != 1:
            heapq.heappop(hp2)
        while hn2 and ip[-hn2[0]] != 0:
            heapq.heappop(hn2)
        p = hp[0] if hp else N + 2
        n = hn[0] if hn else N + 2
        p2 = -hp2[0] if hp2 else -1
        n2 = -hn2[0] if hn2 else -1
        if S[1] == ')' or S[-2] == '(':
            print('NO')
            continue
        if val == 0:
            print('YES') if p == n or (p < n and p2 < n2) else print('NO')
        else:
            print('YES') if p < n and p2 < n2 else print('NO')
    return
solve()

Solution (Python):
import sys
import heapq
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def check(S, idx):
    return 1 if S[idx] == S[idx - 1] or S[idx] == S[idx + 1] else 0

def helper(S, idx):
    res = [-1, -1, -1]
    if S[idx] == '(' and check(S, idx):
        res[1] = 1
    elif S[idx] == ')' and check(S, idx):
        res[1] = 0
    if idx > 1:
        idx -= 1
        if S[idx] == '(' and check(S, idx):
            res[0] = 1
        elif S[idx] == ')' and check(S, idx):
            res[0] = 0
        idx += 1
    if idx < len(S) - 2:
        idx += 1
        if S[idx] == '(' and check(S, idx):
            res[2] = 1
        elif S[idx] == ')' and check(S, idx):
            res[2] = 0
        idx -= 1
    return res

def solve():
    (N, q) = map(int, input().split())
    S = list(''.join(['#', input().strip(), '#']))
    Q = [int(input()) for _ in range(q)]
    ip = [-1] * (N + 2)
    val = 0
    (hp, hn) = ([], [])
    (hp2, hn2) = ([], [])
    for i in range(1, N + 1):
        if S[i] == S[i - 1] or S[i] == S[i + 1]:
            if S[i] == '(':
                heapq.heappush(hp, i)
                heapq.heappush(hp2, -i)
                ip[i] = 1
            else:
                heapq.heappush(hn, i)
                heapq.heappush(hn2, -i)
                ip[i] = 0
        val += 1 if S[i] == '(' else -1
    for idx in Q:
        if val % 2:
            print('NO')
            continue
        val += 2 if S[idx] == ')' else -2
        res = [[], []]
        res[0] = helper(S, idx)
        S[idx] = ')' if S[idx] == '(' else '('
        res[1] = helper(S, idx)
        for i in range(3):
            if res[0][i] != res[1][i] and res[1][i] != -1:
                heapq.heappush(hp, idx - 1 + i) if res[1][i] == 1 else heapq.heappush(hn, idx - 1 + i)
                heapq.heappush(hp2, -(idx - 1 + i)) if res[1][i] == 1 else heapq.heappush(hn2, -(idx - 1 + i))
            ip[idx - 1 + i] = res[1][i]
        while hp and ip[hp[0]] != 1:
            heapq.heappop(hp)
        while hn and ip[hn[0]] != 0:
            heapq.heappop(hn)
        while hp2 and ip[-hp2[0]] != 1:
            heapq.heappop(hp2)
        while hn2 and ip[-hn2[0]] != 0:
            heapq.heappop(hn2)
        p = hp[0] if hp else N + 2
        n = hn[0] if hn else N + 2
        p2 = -hp2[0] if hp2 else -1
        n2 = -hn2[0] if hn2 else -1
        if S[1] == ')' or S[-2] == '(':
            print('NO')
            continue
        if val == 0:
            print('YES') if p == n or (p < n and p2 < n2) else print('NO')
        else:
            print('YES') if p < n and p2 < n2 else print('NO')
    return
solve()