Bedao Regular Contest 11 - EVENSUM

Xem dạng PDF

Gửi bài giải


Điểm: 0,50 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Khánh rất thích đố mọi người giải đố, đặc biệt là với các dãy số. Cho dãy số nguyên ~a_1, a_2, a_3, ... a_n~ và ~Q~ thao tác thuộc ~1~ trong ~2~ loại sau:

  • Cho ba số nguyên ~1, k, b~ và gán ~a_k = b~.
  • Cho ba số nguyên ~2, l, r~. Hãy in ra số lượng đoạn con nằm trong đoạn ~[l, r]~ có tổng là số chẵn.

Input

  • Dòng đầu chứa ~2~ số nguyên ~N~ và ~Q~ ~(1 \le N, Q \le 10^5)~
  • Dòng tiếp theo chứa dãy số nguyên ~a_1, a_2, a_3, ... a_n~ ~(1 \le a[i] \le 10^5)~
  • Dòng thứ ~i~ trong ~Q~ dòng tiếp theo gồm ~3~ số nguyên ~(1 \le k \le N,1 \le b \le 10^5,1 \le l \le r \le N \le 10^5)~ mô tả một trong hai thao tác nêu ở đầu bài.

Output

  • Nếu là thao tác ~2~ hãy in ra số lượng đoạn con nằm trong đoạn ~[l, r]~ có tổng là số chẵn.

Sample Input

7 6
3 2 5 4 8 3 4
1 1 4
1 2 3
2 1 4
1 3 3
2 4 6
1 2 7

Sample Output

6
3

Note

  • Thao tác ~1~, cập nhật ~a_1 = 4~.
  • Thao tác ~1~, cập nhật ~a_2 = 3~.
  • Thao tác ~2~, in ra số lượng đoạn con trong đoạn ~[1,4]~ có tổng là số chẵn.
  • Thao tác ~1~, cập nhật ~a_3 = 3~.
  • Thao tác ~2~, in ra số lượng đoạn con trong đoạn ~[4,6]~ có tổng là số chẵn.
  • Thao tác ~1~, cập nhật ~a_2 = 7~.

Bình luận

Hãy đọc nội quy trước khi bình luận.