---
# System prepended metadata

title: 'CHV training [1]'

---

---
title: CHV training [1]
---

## Bedao Regular Contest 11 - EVENSUM

___
> ###### Tags: Segment Tree.
> https://oj.vnoi.info/problem/bedao_r11_evensum
___
### **Nhận xét** : 
+ Giả sử gọi $s_i = a_1 + a_2.. + a_i$.
+ Ta có thể nhận ra rằng một đoạn $[l, r]$ có tổng là chẵn khi $s_r$ và $s_{l-1}$ cùng chẵn hay cùng lẻ. Từ đó suy ra số đoạn con của đoạn $[l, r]$ có tổng chẵn sẽ là : 
    + Gọi lần lượt $\;x, \;y\;$ là số lượng $s_i$ có tổng là chẵn và lẻ trong đoạn $[l - 1, \; r]$ .
    + Số đoạn con = $x \;* \;(x - 1) \;/ \;2 \;+\; y\; * \;(y - 1)\; / \;2$.
+ Với mỗi truy vấn $1 \:\: k \:\: b$:   
    + Nếu $\;a_k\;$ và $\;b\;$ cùng chẵn hoặc cũng lẻ thì không thay đổi bất cứ điều gì !
    + Ngược lại tất cả những $s_i (k <= i <= n)$ sẽ thay đổi tính chất, từ chẵn thành lẻ và ngược lại.

$=>$ Từ những nhận xét trên ta có thể dùng **Segment Tree** để quản lí tính chất chẵn lẻ của các $s_i$.

> Bạn có thể tham khảo bài : https://oj.vnoi.info/problem/lites/. Để giải được bài này !.
