toilanvd_HSGS's blog

Queries with brackets
By toilanvd_HSGS, 10 years ago, In English

A have some problems with this, could somebody solve it? Thanks!

Give you a string S with N elements, each element is '(' or ')', and M queries, each query has form (x,y), you have to find maximum length of a correct bracket string in the substring from S[x] to S[y].

A sample test:

Input:

()()(()()(

2

1 7

7 10

Output:

4

2

(Limit: 1 <= N, M <= 200000)

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

ignore

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Deleted because it's the solution to another problem

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    problem in this link — find subsequence, but asking for substring.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Here asks for substring , but your given link asks for subsequence

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My bad, I read it wrong. I'm sorry

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

It took me 20 minutes to find a solution and took me 1 hour to write it >.<

This is my solution:

http://paste.ubuntu.com/7971453/

P/S: My algorithm runs in O(1) for each query. My editorial is very complex, but please sympathize me, I did my best. You can believe that it is right. Comment anything if you didn't understand about that.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +13 Vote: I do not like it

    This test: ()()()()() and query (1,10) -> the answer is 10, it is in case 1. However according to case 1 we have |()()()()()| = |_()_()_()_()_()_| = |_Tree1_Tree2_Tree3_Tree4_Tree5_|, and with your algorithm, the answer is 2. Still OK, I think processing this problem is not hard, thank you very much ^_^!

    → Reply