Thống kê dải thu nhập động

Bối cảnh và bài toán

Một doanh nghiệp quản lý mức thu nhập của n nhân sự. Các mức thu nhập có thể thay đổi theo thời gian, đồng thời bộ phận phân tích thường xuyên hỏi có bao nhiêu người đang nằm trong một khoảng giá trị [a,b]. Miền giá trị lớn nên không thể tạo trực tiếp một mảng đếm theo toàn bộ trục số.

Yêu cầu

Xử lý các cập nhật mức thu nhập và truy vấn đếm theo khoảng.

Input

• Dòng 1 chứa n q.
• Dòng 2 chứa n mức thu nhập ban đầu.
• ! k x: đổi giá trị của nhân sự k thành x.
• ? a b: đếm số nhân sự có giá trị trong [a,b].

Output

In kết quả cho mỗi truy vấn bắt đầu bằng ?.

Ràng buộc

• 1 <= n, q <= 2 * 10^5
• 1 <= p[i], x, a, b <= 10^9
• 1 <= k <= n
• a <= b

Chấm điểm

Ví dụ 1

Input

5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3

Output

3
2

Giải thích. Sau khi người 3 tăng từ 2 lên 6, khoảng 2..3 còn hai người.

Ví dụ 2

Input

4 5
10 20 30 40
? 1 100
! 2 50
? 15 45
? 50 50
? 1 9

Output

4
2
1
0

Giải thích. Các truy vấn bao gồm khoảng rộng, biên chính xác và khoảng rỗng về dữ liệu.

Thông tin bài tập

• Yêu cầu ngoài OJ: nộp Decision Note theo template đi kèm.

Nguồn: Phỏng theo CSES – Salary Queries.