Module: Segment ağacı


Problem

2 /4


Segment ağacı

Theory Click to read/hide

Error

Problem

Corwin ve Blaze, Eric'i devirmek için Amber'ı istila etmeye hazırlanır. Bunu yapmak için bir ordu kurmaları gerekiyor. Bulundukları dünyada araziden dolayı bir sıra halinde dizilmiş n yerleşim yerleri vardır. İlk yerleşimde a1, ikinci yerleşimde a2 savaşçı olduğu biliniyor. i -th - ai, n-th - an. 
Bazen Corwin ve Blaze, ai yerleşiminde beklenenden farklı sayıda savaşçı olduğunu öğrenir. Corwin ve Blaze size m kez bir yerleşim yerinin en fazla savaşçıyı sağlayabileceği maksimum savaşçı sayısını soruyor. Tanımlamalarına yardımcı olun.

Giriş
İlk satırda n ve m (1 <= n, m <= 100000) sayıları girilir - sayısı yerleşimler ve istek sayısı .
İkinci satırda n sayılar a1, a2 >, ..., an (1 <= ai <= 1000) - yerleşim yerlerindeki savaşçı sayısı.< /div >
Aşağıdaki m satırları t, l ve r ( 1 <= l <= r <= n), (0 <= t <= 1) - eğer t 0'a eşitse, o zaman l ve r - sorgu sınırları. Aksi takdirde l şehir numarasıdır ve r yeni bilgidir.

Künye
i-th satırında, ti=0 ise i-th sorgusunun yanıtını yazdırın, aksi takdirde "-1" yazdırın.

 
Örnekler
 

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!

# Girdi Çıktı
1
5 3
1 2 3 4 5
0 1 5
1 3 6
0 1 5
5
-1
6