All Tracks Data Structures Advanced Data Structures Segment Trees Problem

( Problem F ) Pikachu and Team Rocket

Advanced Data Structures, Data Structures, Medium-Hard, Segment tree


Team Rocket is back with $$ N $$ of their Pokemon to trouble Pikachu. The Team Rocket's Pokemon are numbered from $$ 1 $$ to $$ N$$ and the $$i^{th}$$ pokemon has health equal to $$a_i $$ 

Pikachu has to battle multiple Pokemon simultaneously. In a single battle, Team Rocket will make Pikachu fight against all the Pokemon in the range $$ [l,r] $$. Pikachu can defeat a Pokemon if his attack value is atleast the Pokemon's health. So, he wants to know the minimum attack he must have to defeat all Pokemon in the range.

However, this time, Team Rocket is stronger than ever. They have designed a technology to modify their Pokemon's health as either of two ways:

  • Type 1: They choose some k (\(1\le k\le N\)), and then health changes as ai = ai+1 (\(k\le i<N\)) and aN = ak.
  • Type 2: They choose some k (\(1\le k\le N\)), and then health changes as ai = ai-1 (\(1< i\le k\)) and a1 = ak.

Note that, all health changes occur simultaneously.

There will be $$ Q $$ events. Each event will be either a battle, or some modification of Pokemon's health by Team Rocket. 

For each battle, help Pikachu by finding the minimum attack value he must have to win against all Pokemon in the range.


  • \(1\le N,Q\le 200000\)
  • \(1\le a_i\le 10^9\)
  • In case of battling event, \(1\le l\le r\le N\)
  • In case of modification event, \(1\le k\le N\)

Input format:

  • First line contains two space separated integers, $$ N $$ and $$ Q $$
  • Second line contains initial health values of $$ N $$ Pokemon
  • Nex $$Q$$ lines contain one event each
  • If the event is a battle, the line contains $$ 1 \hspace{0.2cm} l \hspace{0.2cm} r $$ where $$[l..r] $$ is the range of Pokemon.
  • If the event is modification of type p (\(1\le p\le 2\)), the line contains $$2 \hspace{0.2cm} p \hspace{0.2cm} k $$ where $$ k $$ is the index chosen by Team Rocket. 

Output format:

  • Output one line each for a battling event, containing the minimum attack value required to defeat all Pokemon in the range.
5 5
100 200 300 400 500
1 2 5
2 2 4
1 1 2
2 1 2
1 3 5

  1. In the range $$ [2,5] $$, the maximum health is $$ 500 $$.
  2. The new strengths of pokemon are $$ [400, 100, 200, 300, 500] $$.
  3. In the range $$ [1,2] $$, the maximum health is $$ 400 $$.
  4. The new strengths of pokemon are $$ [400, 200, 300, 500, 100] $$.
  5. In the range $$ [3,5] $$, the maximum health is $$500$$ .
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

August Easy '18

View All Notifications