409989: GYM103886 P Cereal Mountains

Agastya, the king of the Cereal Kingdom, loves to use his god powers to create cereal mountains.

More specifically, Agastya's Cereal Kingdom is described as and array length $$$n$$$ of heights $$$h_1, h_2, \dots h_n$$$.

When Agastya casts a spell at position $$$i$$$ with power $$$p$$$ and range $$$r$$$, for all indices $$$1 \leq j \leq n$$$ such that $$$|j - i| \le r$$$, $$$h_j$$$ increases by $$$p \cdot (r - |j-i|)$$$.

Larry is an over achiever, so he always wants to climb up to the tallest mountains near him. Larry is at position $$$p$$$, and wants to know the height of the tallest mountain within distance $$$d$$$ from his current position.

More specifically, Larry wants to know $$$\max(h_i)$$$ such that $$$1 \leq i \leq n$$$ and $$$|i-p| \le d$$$.

Please help Larry find the tallest of the cereal mountains.

The first line contains one integer, $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$.

The next line contains $$$n$$$ integers, describing $$$h_1, h_2, \dots h_n$$$ $$$(1 \leq h_i \leq 10^9)$$$.

The next line contains one integer, $$$q$$$ $$$(1 \leq q \leq 2 \cdot 10^5)$$$.

The $$$i$$$-th line of next $$$q$$$ lines first contains an integer $$$t_i$$$, describing the type of query.

If $$$t_i = 1$$$, then Agastya casts a spell. The query type is followed by $$$3$$$ integers $$$i$$$, $$$p$$$, and $$$r$$$, describing the position, power, and range of the spell $$$(1 \leq i, r \leq n)$$$, $$$(1 \leq p \leq 10^2)$$$.

If $$$t_i = 2$$$, then the query type is followed by two integers $$$p$$$ and $$$d$$$, describing the position of Larry, who wants to know the height of the tallest mountain within distance $$$d$$$ $$$(1 \leq p, d \leq n)$$$.

For each query of type $$$2$$$, print out one integer $$$i$$$ followed by a newline, describing the height of the tallest mountain within distance $$$d$$$ from position $$$p$$$.

5
3 4 0 3 5
4
1 4 5 5
2 5 1
1 2 3 2
2 2 2

25
25

Initially, the $$$h$$$ = $$$[3, 4, 0, 3, 5]$$$.

When Agastya casts a spell at position $$$4$$$ with power $$$5$$$ and range $$$5$$$, the increases are $$$[10, 15, 20, 25, 20]$$$ and $$$h$$$ = $$$[13, 19, 20, 28, 25]$$$.

The tallest mountain within distance $$$1$$$ of index $$$5$$$ is $$$25$$$.

Agastya then casts a spell at position $$$2$$$ with power $$$3$$$ and range $$$2$$$. The increases are $$$[3, 6, 3, 0, 0]$$$, and $$$h$$$ = $$$[16, 25, 23, 28, 25]$$$.

The tallest mountain within distance $$$2$$$ of index $$$2$$$ is $$$25$$$.

Problem Credits: Agastya Goel