Mô tả bài toán: Quản lý lương nhân viên

Một công ty có ~n~ nhân viên với mức lương đã biết. Nhiệm vụ của bạn là quản lý các mức lương và thực hiện các truy vấn.

Input:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~: số lượng nhân viên và số lượng truy vấn.
• Dòng thứ hai chứa ~n~ số nguyên ~p_1, p_2, ..., p_n~: mức lương của từng nhân viên.
• Sau đó có ~q~ dòng mô tả các truy vấn. Mỗi dòng có một trong hai dạng:
  • ! k x: thay đổi mức lương của nhân viên ~k~ thành ~x~.
  • ? a b: đếm số lượng nhân viên có mức lương nằm trong đoạn ~[a, b]~.

Output:

• In ra kết quả cho từng truy vấn ? (đếm số nhân viên trong khoảng lương).

Ràng buộc:

• ~1 \leq n, q \leq 2 \cdot 10^5~
• ~1 \leq p_i \leq 10^9~
• ~1 \leq k \leq n~
• ~1 \leq x \leq 10^9~
• ~1 \leq a \leq b \leq 10^9~

Ví dụ:

Input:

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

Output:

3
2

Giải thích:

1. Ban đầu, lương nhân viên: [3, 7, 2, 2, 5].
2. Truy vấn ? 2 3: Nhân viên 3 nhân viên có lương trong khoảng [2, 3]: (2, 2, 3).
3. Truy vấn ! 3 6: Thay đổi lương nhân viên 3 từ 2 thành 6. Lương mới: [3, 7, 6, 2, 5].
4. Truy vấn ? 2 3: Nhân viên 2 nhân viên có lương trong khoảng [2, 3]: (2, 3).