### PROBLEM LINKS

### DIFFICULTY

SIMPLE

### PREREQUISITES

Range Minimum Query, Simple Math

### PROBLEM

You are given **N** matchsticks arranged in a straight line, with their **rear** **ends** touching each other. You are also given the rate of burn for every matchstick (possibly same) in number of seconds it takes to burn it out. If a matchstick is lit from both ends, it burns out **twice** as fast - taking **half** as much time.

Answer several queries of the following type efficiently

All the matchsticks in the range **L** to **R**, inclusive are lit from their front ends simultaneously. Find how much time it takes for **all** the matchsticks to burn out.

### QUICK EXPLANATION

For each query, the operation performed plays out in the following way

- All the matchsticks in the range
**L**to**R**are lit from their front ends. - The matchstick that burns
**quickest**in the range**L**to**R**burns out and**ignites**all the other matchsticks on their**rear**ends. - The matchticks in the range
**L**to**R**now burn out**twice**as fast. -
**All**the other matchsticks burn out at their**original**rate.

We can find the time taken in all the steps above using only the following pieces of information for the segment **L** to **R**

- Quickest rate of burning for a match in the range
**L**to**R**. - Slowest rate of burning for all matches in the range
**L**to**R**. - Slowest rate of burning for all matches outside the range
**L**to**R**.

### EXPLANATION

For a given range **L** to **R**

- Let
**m**denote the minimum time taken by some matchstick in the range**L**to**R**to burn out - Let
**M**denote the largest time taken by some matchstick in the range**L**to**R**to burn out - Let
**M**’ denote the largest time taken by some matchstick outside the range**L**to**R**to burn out

The time taken by each of the steps in the scenario described above is as follows

- The matchstick that burns quickest, burns out
- Takes time
**m**

- Takes time
- The following things happen in parallel
- The matchsticks in the range
**L**to**R**now burn out twice as fast- Takes time
**(M - m) / 2**

- Takes time
- The matchsticks outside the range
- Takes time
**M’**

- Takes time

- The matchsticks in the range

Thus, the time taken for all the matches to burn out completely is

m + max( (M-m)/2 , M' )

It remains to find efficiently the **minimum** time some matchstick will take in a range, and the **maximum** time some matchstick will take in a **range**.

Such queries can be answered in **O(N log N)** time by using segment trees. Refer to this topcoder tutorial for a wonderful writeup with code samples on how to get about writing a segment tree. The topcoder tutorial also describes a **O(N sqrt(N))** approach as well which will also work within the time limits for this problem.

**Two segment trees must be constructed**. One to answer queries of the type “**minimum in a range**”, that returns the time it takes for the fastest burning matchstick to burn out. Another to answer queries of the type “**maximum in a range**” to find **M** and **M**’ as defined above. Note that **M**’ will itself be the maxmimum of two ranges, **1 to L-1** and **R+1 to N** respectively.

A lot of solutions were stuck in the caveat that it is required to **always** print the answer in a **single** decimal place. Note how the answer will either be **integer**, or contain a single decimal digit (**5**). In case the answer is **integer**, it is required to print a trailing decimal followed by **0**.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Approach - finds range min query in time O(rootN) - solution.

Approach - finds range min query using segment trees in O(logN) - solution.