Editorial for Another Random Contest 1 P4 - Bracket Query

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: andy_zhu23


If two insertions are allowed, one can insert a series of left brackets before L and a series of right brackets after R. It can be shown that it will always generate a valid bracket sequence.

Let's denote all ( as 1 and all ) as -1. We can check whether or not we need to add a series of left brackets by checking the signs of prefix sum. If at any point the prefix sum turns negative, we need to add a series of left brackets. The same thing can be applied to check for right brackets by using postfix sum and check for positive instead of negative.

Subtask 1

Simply enumerate through all positions to check if at any position the prefix sum turns negative or postfix sum turns positive. Output NO if both occur, and YES otherwise.

Time Complexity: \mathcal O(NQ)

Subtask 2

Use any data structure that can answer range minimum query (RMQ), such as a segment tree or sparse table, to find the minimum prefix sum and maximum postfix sum in the interval L, R.

Time Complexity: \mathcal O((N+Q) \log N)


There are no comments at the moment.