What is standard method for this problem?
Using stac I prepeared next[100000] for each opening
and closing brackets.
But it is appeared as bad because 50000*100000 too big.
I made big jumps as next100[100000] and got Ac 0.203
Is my method can be beaten by new tests?

You can use RMQ to solve this problem.

My solution does not use RMQ. And it's just O(N) preprocess and O(1) query answer.

Thank for good advice!
I know RMQ and understood how to apply it in this problem.

Hi! I've solved this task with custom <O(L), O(1)> algo. It is very interesting for me to reduce this problem to RMQ. Can you give me advice (here or by email: different-things[at]nm[dot]ru) ?

Could you explain your custom <O(L), O(1)> solution, please?

A idea i had today, but haven't yet tested using RMQ is this:

0 - Read the input string to str[]
1 - Create an int array val[], where in position i there is the position of the character that pairs with the character str[i]. If there is no such character, val[i] equal to X = -1.

For example:
pos - 0 1 2 3 4 5 6 7 8 9
str - A G g a a G T t c g
val - 3 2 1 0 X X 8 7 X X

2 - For a query (a, b), the program answers "1" if the minimum and maximum values in val[] range [a-1, b-1] are between a and b. "0", otherwise.

I'll see if it works later...

Could you tell me more about your solution ?
Is it sparse tables ?

<O(L), O(log L)> segment tree solution acceptable too =)

To do RMQ, I used a segment tree, but it could have been done using sparse tables too, I think.

The idea, if I remember well, is the one I explained earlier in this topic. I just looked for my solution source code but without success. But i really think the final idea I used was that one.

Remember, this is a problem for school kids, no RMQ is needed.

Make a pointer-based stack, if isupper, then push to it, if islower, check if the current char matches the one on the top of the stack: if so, pop, otherwise discard the stack. For each query check that before l the top of the stack was the same as after r.

Your algo is better not only because it is childish
but due it's  simple nature and then it may be implemented in assembler for example and it is not work for children.

Please explain us, what will you algorithm output to following input:
AaBbA
1
2 5

Before l=2 and after r=5 stack is the same, it is "A", but sequence aBbA is not human.

SQRT-decomposition get TL on Java.

Edited by author 25.06.2011 21:19

Apply the GOOD JOB for College ACMers to Make Large Money and Become a Millionaire

Hello, We need large no. of dedicated and hard working ACMers. The payment is good so we need ACMers to be efficient. All you have to do to get the job is to sign up at our websites. The link of our websites are given below.

http://www.PaisaLive.com/register.asp?3556638-4847933

After the registration, a confirmation email will be sent to your specified email address. Please click on the link inside the confirmation email to activate your account and recieve ACM work instantly. For any other queries you can mail the administrator.

Miss Juliet

Admin paisalive.com

Apply the GOOD JOB for College ACMers to Make Large Money and Become a Millionaire

Hello, We need large no. of dedicated and hard working ACMers. The payment is good so we need ACMers to be efficient. All you have to do to get the job is to sign up at our websites. The link of our websites are given below.

http://www.PaisaLive.com/register.asp?3556638-4847933

After the registration, a confirmation email will be sent to your specified email address. Please click on the link inside the confirmation email to activate your account and recieve ACM work instantly. For any other queries you can mail the administrator.

Miss Juliet

Admin paisalive.com