Блог пользователя Boring_Day

Автор Boring_Day, история, 2 года назад, По-английски

I was solving yesterday's c with a different approach. To solve it with my technique what i need to know is:

Let's say we have a string 's' of length 'n' with parenthesis ('(' or ')') and we have queries with 'L' and 'R' (1<=L<=R<=N).

we need to tell whether the substring from L to R is balanced or not.

Is there any way to solve the queries in constant time or lets say log(n) time?

Please Help.

  • Проголосовать: нравится
  • -15
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

You can store the prefix in array pre. Then make sure that pre[r]-pre[l-1] = 0 and minimum value of pre in [L,R] is >= pre[L-1]. For checking second condition you can use segment tree for O(logn) query or use stack method to precompute next smaller element to query in O(1)