CSES - Salary Queries | Truy vấn Tiền lương

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
BJMinhNhut , tkkhanghuynhminh , MinhCrafter
Dạng bài
Điểm: 1800 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Một công ty có \(n\) nhân viên với mức lương nhất định. Nhiệm vụ của bạn là theo dõi tiền lương và xử lí truy vấn.

Input

Dòng đầu tiên gồm hai số nguyên \(n\) và \(q\): số lượng nhân viên và truy vấn. Các nhân viên được đánh số \(1,2,...,n\).

Dòng tiếp theo gồm \(n\) số nguyên \(p_1, p_2,...p_n\): lương của mỗi nhân viên.

Sau đó, có \(q\) dòng mô tả các truy vấn, mỗi dòng có một trong những dạng sau:

  • ! \(k\) \(x\): thay đổi lương của nhân viên thứ \(k\) thành \(x\)
  • ? \(a\) \(b\): đếm số nhân viên có tiền lương trong khoảng \(a...b\)

Output

  • In ra đáp án cho mỗi truy vấn ?.

Constraints

  • \(1≤n,q≤2⋅10^5\)
  • \(1≤p_i≤10^9\)
  • \(1≤k≤n\)
  • \(1≤x≤10^9\)
  • \(1≤a≤b≤10^9\)

Example

Test

Input 
5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3
Output 
3
2

Bình luận