### PROBLEM LINK:

**Author:** Hasan Jaddouh

**Primary Tester:** Prateek Gupta

**Editorialist:** Hussain Kara Fallah

### PROBLEM EXPLANATION

There are **N** hills located on a straight line. The height of the **i ^{th}** one is denoted by

**H**. A participant standing at the top of the

_{i}**i**hill jumps to the nearest hill to the right which is strictly higher than the one he is standing on. If the nearest one is further than 100 hills away, he doesn’t move anywhere.

^{th}Giving Q queries of 2 types:

The first type is given by **(P,K)** , a participant standing on the **P ^{th}** hill is willing to perform K successive moves, what hill he will be ending at?

The second type is given by **(L,R,X)**, for each hill between the **L ^{th}** one and the

**R**one (inclusive) should be increased by X (it may be negative).

^{th}### DIFFICULTY:

medium

### PREREQUISITES:

Complexity Analysis, Sqrt decomposition

### EXPLANATION:

Let’s define an array **nxt[N]** where **nxt _{i}** denotes the next hill the participant standing at the

**i**hill is going to jump to (or

^{th}**nxt**if he cannot jump to any other hill).

_{i}=iLet’s break our hills into blocks, each block consisting of exactly S=\sqrt{n} hills.

As you can guess, keeping only the next hill we would jump to from each one, is not really effective. That’s because jumping hills one by one will lead us to at least **O(Q * K)** solution which exceeds the time limit indeed. Maintaining a sparse table is not a really good idea also, because modifying an element in a sparse table may lead you modifying the whole table.

Let’s make something similar to sparse table, Let’s define a table **F[N]**. For the **i ^{th}** hill let

**F**denotes the furthest hill

_{i}**(which is located in the same bucket)**that we can reach via successive jumps starting from the

**i**hill (and how many jumps we need to reach it).

^{th}Assuming both of our tables **F[],nxt[]** are fixed, then answering queries of the first type would be quite easy. Let’s repeatedly jump to the last hill in the current bucket as long as we are not exceeding the remaining jumps, after that moving 1 bucket forward via **nxt[]** table. So any number of jumps would be decomposed into at most \sqrt{n} mass jumps. At a point if a bucket was longer to finish than the remaining jumps, let’s just find our destination by processing it linearly. So the first query is answered in O(\sqrt{n})

Let’s discuss modifying our arrays.

Regarding modifying heights, this is a naive application of sqrt decomposition which can be done in O(\sqrt{n}), by updating blocks which were included partially in the query in a linear search. Regarding blocks that were completely included into the query we may increment the variable denoting the sum of increments applied to this bucket (each bucket should have a variable).

### Observations:

For each **i** such that **(i > R) :: nxt _{i}** will stay the same.

It’s obvious because all participants are jumping to the right. Starting from the **(R+1) ^{th}** hill, no hill will be changed.

For each **i** such that **(i < L-100) :: nxt _{i}** will stay the same, that’s because a participant cannot skip more than 100 hills, so for each

**i**in the previous range,

**(i+100 < L**), so

**no**participant would be allowed to jump to a hill that is modified through our query.

Consider the **i ^{th}** hill, if

**nxt**and we apply the

_{i}=j**QUERY(L,R,X)**for any

**(L ≤ i AND R ≥ j)**then the value of

**nxt**won’t change, that’s because the

_{i}**j**hill is the closest strictly higher hill (to the

^{th}**i**one), and applying the same query to all hills between won’t change the relative order between any pair of them.

^{th}For each **i** such that **(R-100 < i ≤ R) :: nxt _{i}** will be modified and needs to be calculated again.

For each **i** such that **(L-100 ≤ i < L) :: nxt _{i}** will be modified and needs to be calculated again.

As a conclusion, you can see that the **nxt** value of around 200 hills will be changed. We can process this in nearly O(400) by maintaining a stack. Regarding our table **F** modification, we should process each bucket that contains at least one hill which has its nxt variable modified. We should process each bucket linearly from right to left and maintain a stack during that. All modified buckets should have its data refreshed. Modification query can be done in O(400 + \sqrt{n})

### AUTHOR’S AND TESTER’S SOLUTIONS:

**AUTHOR’s solution**: Can be found here

**TESTER’s solution**: Can be found here