Đếm số chẵn và lẻ

Trong một buổi thảo luận về toán học, FullHouse Dev đã được giao một bài toán thú vị. Họ cần phải xử lý một mảng các số tự nhiên và thực hiện một số truy vấn để kiểm tra tính chất của các số trong mảng. Nhiệm vụ của nhóm là giải quyết các truy vấn liên quan đến việc sửa đổi mảng và đếm số lượng số chẵn và số lẻ trong một khoảng cho trước.

Bài toán

FullHouse Dev nhận được một mảng \(A\) gồm \(N\) số tự nhiên. Họ cần thực hiện các truy vấn sau:

• Truy vấn 0: sửa đổi phần tử tại chỉ số \(i\) thành \(x\).
• Truy vấn 1: đếm số lượng số chẵn trong khoảng từ \(l\) đến \(r\) (bao gồm cả \(l\) và \(r\)).
• Truy vấn 2: đếm số lượng số lẻ trong khoảng từ \(l\) đến \(r\) (bao gồm cả \(l\) và \(r\)).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\) - số lượng phần tử trong mảng.
• Dòng tiếp theo chứa \(N\) số tự nhiên - các phần tử của mảng.
• Dòng tiếp theo chứa số nguyên \(Q\) - số lượng truy vấn, tiếp theo là \(Q\) truy vấn.
• Mỗi truy vấn có dạng:
  • 0 x y - sửa đổi số tại chỉ số \(x\) thành \(y\).
  • 1 x y - đếm số lượng số chẵn trong khoảng từ \(l\) đến \(r\).
  • 2 x y - đếm số lượng số lẻ trong khoảng từ \(l\) đến \(r\).

OUTPUT FORMAT:

• Đối với mỗi truy vấn đếm, in ra kết quả tương ứng.

Ràng buộc:

• \(1 \leq N, Q \leq 10^5\)
• \(1 \leq l \leq r \leq N\)
• \(0 \leq A[i] \leq 10^9\)
• \(1 \leq x \leq N\)
• \(0 \leq y \leq 10^9\)

VÍ DỤ

INPUT

6
1 2 3 4 5 6
4
1 2 5
2 1 4
0 5 4
1 1 6

OUTPUT

2
2
4

Giải thích

• Trong ví dụ trên, truy vấn đầu tiên yêu cầu đếm số lượng số chẵn trong khoảng từ 2 đến 5, kết quả là 2. Truy vấn thứ hai yêu cầu đếm số lượng số lẻ trong khoảng từ 1 đến 4, kết quả cũng là 2. Sau khi sửa đổi phần tử tại chỉ số 5 thành 4, truy vấn cuối cùng yêu cầu đếm số lượng số chẵn trong khoảng từ 1 đến 6, kết quả là 4.