Subtask 1. ~n \le 10^2~

Sử dụng hai vòng lặp ~(i, j)~ thể hiện dãy đang kiểm tra. Sau đó, sử dụng thêm một vòng lặp để tính tổng, và kiểm tra tính chẵn lẻ của tổng tìm được.

Độ phức tạp: ~O~ (~n^3~).

Subtask 2. ~n \le 5 \times 10^3~

Sử dụng mảng cộng dồn để tính nhanh tổng của một đoạn con ~(i, j)~ thay vì duyệt lại.

Độ phức tạp: ~O~ (~n^2~).

Subtask 3. ~n \le 10^5~

Xem xét đoạn con ~(i, j)~, với ~f~ là mảng cộng dồn tương ứng. Để ~(i, j)~ là một cặp thỏa mãn, ta cần ~f_j - f_{i - 1}~ là chẵn, hay ~f_j~ và ~f_{i - 1}~ cùng tính chẵn lẻ.

Vì vậy, ta duy trì ~cnt_0~ là số phần tử ~f_i~ (~i < j~) mà ~f_i~ chẵn, khi ta duyệt ~j~. Tương tự ta duy trì ~cnt_1~ nhưng với ~f_i~ lẻ. Ban đầu, ~cnt_0 = 1~, do ~f_0 = 0~ là chẵn.

Khi ta duyệt tới ~j~, nếu ~f_j~ chẵn, thì kết quả tăng thêm ~cnt_0~. Nếu ~f_j~ lẻ, kết quả tăng thêm ~cnt_1~.

Sau đó, nếu ~f_j~ chẵn, ~cnt_0~ tăng thêm ~1~. Ngược lại, ~cnt_1~ tăng thêm ~1~.

Đến đây, ta đã vô tình tính cả các đoạn con chỉ có một phần tử. Ta duyệt lại cả mảng, nếu ~a_i~ chẵn, thì đoạn con chỉ gồm phần tử ~i~ đã được đếm thừa. Ta trừ kết quả đi ~1~.

Độ phức tạp: ~O~ (~n~).