Bài toán: Đếm số dãy con có tổng bằng 0

Mô tả:

Trong tiết học hôm nay, thầy Alex giảng về các dãy số có tổng các phần tử bằng ~0~. Để giúp Bob - học sinh xuất sắc nhất lớp, thầy đưa ra bài toán:

Cho một dãy số nguyên ~A~ gồm ~N~ phần tử, hãy tính số lượng dãy con liên tiếp khác rỗng của ~A~ mà tổng các phần tử bằng ~0~.

• Một dãy con liên tiếp được coi là khác nhau nếu chúng có ít nhất một vị trí khác biệt.

Input:

• Dòng thứ nhất ghi số nguyên dương ~N~ là số lượng phần tử trong dãy ~A~ ~(1 \leq N \leq 2 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(-10^9 \leq A_i \leq 10^9)~.

Output:

• In ra một số nguyên là số lượng các dãy con liên tiếp khác rỗng có tổng bằng ~0~.

Ràng buộc:

• ~1 \leq N \leq 2 \times 10^5~.
• ~-10^9 \leq A_i \leq 10^9~.
• Tất cả dữ liệu đều là số nguyên.

Ví dụ:

Input:

6
-6 0 1 2 3 -6

Output:

4

Giải thích:

• Các dãy con liên tiếp có tổng bằng ~0~ là:
  • ~[-6, 0, 1, 2, 3, -6]~,
  • ~[0]~,
  • ~[1, 2, 3, -6]~,
  • ~[-6, 0, 1, 2, 3]~.