Truy vấn lương (Salary Queries)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một công ty có $n$ nhân viên, nhân viên $i$ có mức lương hiện tại $p_i$. Có $q$ truy vấn:

• ! k x: đổi lương của nhân viên $k$ thành $x$.
• ? a b: đếm số nhân viên có mức lương thuộc đoạn $[a,b]$.

Input

Dòng đầu chứa $n,q$.

Dòng thứ hai chứa $p_1,p_2,\ldots,p_n$.

$q$ dòng tiếp theo là các truy vấn.

Output

Với mỗi truy vấn ?, in số nhân viên thỏa điều kiện.

Subtask

• Subtask 1 — 20%: $1\le n,q\le50$.
• Subtask 2 — 30%: $1\le n,q\le5000$.
• Subtask 3 — 50%: $1\le n,q\le2\cdot10^5$, các mức lương và biên truy vấn thuộc $[1,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

Ban đầu có ba mức lương thuộc $[2,3]$: $3,2,2$. Sau khi đổi lương nhân viên $3$ từ $2$ thành $6$, chỉ còn hai người trong đoạn.