|
|
back to boardI'm not good at English.
A[I] is the Ith number.
First,try to count a array F.
F[I] means the nearest number A[F[I]]:
A[F[I]]>A[I] and F[I]>I.
You can count F in O(N).
Find largest number in [L,R],just find a min I,F[I]>R.
So you can solve the problem in O(N+M).
And this problem is RMQ problem, also have a very hard standard solution in O(N+M).
Edited by author 07.05.2004 20:31 Good idea. But I had to be very carefully solving it.
Edited by author 04.05.2006 20:00 Thanks, @Ted.
Your idea is brilliant.
I count F[] array with O(N) , used stack.
+ buffered i/o ==> result is very good: AC. 0.001s There is an interesting situation here: when I declared arrays a and f with size 1..25000, I got WA#2. When I changed them to 1..25001, I got AC... I have used rather simple method, I have organized four stacks, first two to make a queue of M size, and others to store max elements of queue, by this way you can find elements in constant time. Very useful for Java, you have Class Stack. I have used rather simple method, I have organized four stacks, first two to make a queue of M size, and others to store max elements of queue, by this way you can find elements in constant time. Very useful for Java, you have Class Stack. Thanks for sharing the idea... :) |
|
|
