Centre for Gifted Education - Hanoi university of Technology

   

Fast traslate

Icon translate

Trước khi giải bài này, bạn cần có 1 khái niệm cũng như các phương thức của nó. Khái niệm về Interval Tree

Bài toán đặt ra:
Cho một dãy số có độ dài N gồm các số nguyên (đánh số từ 1 -> N). Người ta có M request gồm 2 loại sau:
1 ij: Thay phần tử bằng j value.
2 ij: xuất ra tổng số các phần tử trong dãy số, từ vị trí tôi đến vị trí j.

Đầu vào

First line chứa 2 N và M số nguyên.

Thứ 2 dòng chứa các dãy phần tử.

Last M line chứa các yêu cầu.

Đầu ra

Strate a number of match the lines is results of the Q request in the file input.

Limit

1 <= n <= 10000

| ai | <= 1000

1 <= m <= 100000

Thí dụ

Đầu vào:

5 3 
1 2 3 4 5 
2 2 3 
1 3 7 
2 1 4 

Đầu ra: 5 14