Module: 세그먼트 트리


Problem

2 /4


세그먼트 트리

Theory Click to read/hide

Error

Problem

코윈과 블레이즈는 에릭을 전복시키기 위해 앰버를 침공할 준비를 합니다. 그러기 위해서는 군대를 키워야 합니다. 그들이 위치한 세계에는 지형으로 인해 일렬로 정렬된 n개의 정착지가 있습니다. 첫 번째 정착지에는 a1 전사가 있고 두 번째 정착지에는 a2가 있는 것으로 알려져 있습니다. i -th - ai, in n-th - an. 
때때로 Corwin과 Blaze는 ai 정착지의 전사 수가 예상과 다르다는 것을 알게 됩니다. Corwin과 Blaze는 정착지가 가장 많은 전사를 공급할 수 있는 최대 전사 수를 m배로 묻습니다. 식별할 수 있도록 도와주세요.

입력
첫 번째 줄에 숫자 n 및 m (1 <= n, m <= 100000)이 입력됩니다. 합의 및 요청 수 .
두 번째 줄에는 n 숫자 a1, a2 >, ..., an (1 <= ai <= 1000) - 정착지의 전사 수.< /사업부 >
다음 m 줄에는 숫자 t, l 및 r ( 1 <= l <= r <= n), (0 <= t <= 1) - t 가 0과 같으면 l 및 r - 쿼리 경계. 그렇지 않으면 l은 도시 번호이고 r은 새로운 정보입니다.

출판물
i번째 줄에 ti=0인 경우 i번째 쿼리에 대한 답변을 인쇄하고 그렇지 않은 경우 인쇄 "-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