RMQ (Range Minimum Query), who r u?

[allornothing]

I'm newcomer, so help me pls!
What's the RMQ problem?

[Larry]

The RMQ problem is a very interesting problem.

The problem itself is just as simple as finding the minimum element between two indices.

The naive solution can be < O( n^2 ), O( 1 ) > or < O( 1 ), O( n ) > (< Preprocess, Query>). It can be done cleverly in <O( n log n ), O( 1 )>. In fact, the general RMQ problem reduces to the LCA problem, which can be reduced to the +/- 1 RMQ problem, which can be solved in <O( n ), O( 1 )>.

There are a few good short papers on this, so perhaps you should look it up.. the math is fun!

[allornothing]

Thanks!
And what's about this problem, does the solution use RMQ? How to solve?

Problem 7: Cave Cows 2 [Brian Dean, 2004]

In one cave Bessie is planning to explore, a long corridor is made
up of N segments (1 <= N <= 25,000 and numbered 1..N) joined
end-to-end. Each of these segments has a particular width which
can only be traversed by a cow whose "fatness" index is no larger
than that width. A cow can travel along a sequence i..j of these
segments only if its fatness index is no larger than the minimum width
of all of those corridors. Corridor widths are integers in the
range 1..1,000,000,000.

In order to plan her caving expedition, Bessie needs to answer a
collection of Q (1 <= Q <= 25,000) queries of the form "what is the
maximum fatness of a cow that can pass through the sequence i..j
of corridors?". Please help Bessie with her dilemma.

PROBLEM NAME: cavecow2

INPUT FORMAT:

* Line 1: Two space-separated integers, N and Q

* Lines 2..N+1: Each line gives the integer width of a corridor. Line
2 describes corridor 1; line 2 describes corridor 2; and so
on.

* Lines N+2..N+Q+1: Each line corresponds to a query and contains two
space-separated integers i and j (where i < j), giving the
indices of the corridors at both ends of the query interval.

SAMPLE INPUT (file cavecow2.in):

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

OUTPUT FORMAT:

* Lines 1..Q: Each line contains the integer answer to a query

SAMPLE OUTPUT (file cavecow2.out):

5
38
20
5

[Gigi's Baby]

Hi,
Could anyone tell me which problems in UVA are RMQ or LCA problems ?

[nibbler]

I solved Cave Cows 2 like this: divide the segments into groups of 50, and preprocess the min of every group. Example querry: what is min from 117 to 873?
Compute "manually" min from 117 to 150, then you now mins from 150-200, 200-250, ... , 800-850, then manually from 850-873 again. Maximal time to answer queries is 150 operations, and I think it ran fast enough.
General solution can be also short, try googling.