Module: セグメントツリー


Problem

2 /4


セグメントツリー

Theory Click to read/hide

Error

Problem

コーウィンとブレイズは、エリックを倒すためにアンバーに侵入する準備をします。これを行うには、軍隊を編成する必要があります。それらが位置する世界では、地形のために n 個の集落が一列に並んでいます。最初の入植地には a1 人の戦士がいて、2 番目の入植地には a2 の戦士がいることが知られています。 i 番目 - ai、n 番目 - an. 
コーウィンとブレイズは、ai の入植地に予想とは異なる数の戦士がいることに気付くことがあります。 Corwin と Blaze は m 回、集落が最も多くの戦士を供給できる戦士の最大数を尋ねます。

入力
最初の行では、数値 n  と m (1 <= n, m <= 100000) が入力されています - の数決済とリクエスト数 .
2 行目には n 数字 a1, a2 >, ..., an (1 <= ai <= 1000) - 入植地の戦士の数.< /div >
次の m 行には、数値 t、l 、および r ( 1 <= l <= r <= n), (0 <= t <= 1) - t  が 0 に等しい場合l and r - クエリ境界。それ以外の場合 l は都市番号、r は新しい情報です。

インプリント
i 番目の行に、ti=0 の場合は i 番目のクエリに対する回答を出力し、それ以外の場合は出力します。 print "-1".

 
例
<頭> <本体>
 

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# 入力 出力
1
5 3
1 2 3 4 5
0 1 5
1 3 6
0 1 5
5
-1
6