PROBLEM LINK:Author: Vaibhav Gosain Editorialist: Vaibhav Gosain DIFFICULTY:MediumHard PREREQUISITES:Segment Trees PROBLEM:Given a string containing only '(' and ')', you have to handle 2 types of operations on it:
The length of the string is N , and you have to handle Q operations. EXPLANATION:Can be solved via segment tree: Things to maintain at every segment tree node:
Using these, we can perform range_flip operation in O(logN) per query. You can refer to the Author's solution for more details: Link For query 2 x we need to find first position greater than (x1) with prefix sum less than the prefix sum at position (x1). When we range query in a segment tree, it is divided into O(logN) complete node ranges. Find the first range from the left side which has range minimum less than prefix sum at x1. We can now find the first point in that range with the required prefix sum. Time Complexity: O((N+Q)*log(N)) AUTHOR'S SOLUTION:Author's solution can be found here. asked 03 Oct '16, 22:05
