Balanced Brackets using Segment Tree - BRCKTS

test1.py

from math import ceil,log
 
class node:
	def __init__(self):
		self.needLeft = 0
		self.needRight = 0
 
def construct(arr,index,start,end):
	global tree
	if start == end:
		if arr[start] == '(':
			tree[index].needRight = 1
		else:
			tree[index].needLeft = 1
	else:
		mid = (start+end)//2
		construct(arr,2*index,start,mid)
		construct(arr,(2*index)+1,mid+1,end)
		newMatches = min(tree[2*index].needRight,tree[(2*index)+1].needLeft)
		tree[index].needLeft = tree[2*index].needLeft + tree[(2*index)+1].needLeft - newMatches
		tree[index].needRight = tree[2*index].needRight + tree[(2*index)+1].needRight - newMatches
 
def modify(index,startIndex,start,end):
	global tree
	if start == end:
		if tree[startIndex].needLeft == 1:
			tree[startIndex].needLeft = 0
			tree[startIndex].needRight = 1
		else:
			tree[startIndex].needLeft = 1
			tree[startIndex].needRight = 0
		return 
	else:
		mid = (start+end)//2
		if index <= mid:
			modify(index,2*startIndex,start,mid)
		else:
			modify(index,(2*startIndex)+1,mid+1,end)
		newMatches = min(tree[2*startIndex].needRight,tree[(2*startIndex)+1].needLeft)
		tree[startIndex].needLeft = tree[2*startIndex].needLeft + tree[(2*startIndex)+1].needLeft - newMatches
		tree[startIndex].needRight = tree[2*startIndex].needRight + tree[(2*startIndex)+1].needRight - newMatches
 
for testcase in range(1,11):
	print("Test " + str(testcase)+":")
	n = int(input())
	arr = input()
	height = ceil(log(n,2))
	tree = [node() for _ in range(0,2**(height+1))]
	construct(arr,1,0,n-1)
	m = int(input())
	for _ in range(0,m):
		k = int(input())
		if k == 0:
			if tree[1].needLeft == 0 and tree[1].needRight == 0:
				print("YES")
			else:
				print("NO")
		else:
			modify(k-1,1,0,n-1)