Dễ thấy trong đoạn mã giả ở đề bài, ta có ~1 \le i < j < x < y \le n~.

Bài toán từ đó trở thành đếm số bộ bốn phần tử phân biệt của dãy ~a~ có tổng bằng ~0~.

Gọi ~cnt[pos][sum]~ là số lượng cặp ~(i, j)~ sao cho ~1 \le i < j \le pos~ và ~a[i] + a[j] = sum~.

Giả sử tính được mảng ~cnt~ trên. Khi đó đáp án của bài toán là tổng của các ~cnt[x - 1][-(a[x] + a[y])]~ với mọi cặp ~(x, y)~ sao cho ~3 \le x < y \le n~.

Tuy nhiên, ta không thể lưu dữ liệu vào một mảng ~cnt[pos][sum]~ được vì ~-2\times 10^6 \le sum \le 2\times 10^6~ và ~pos \le n~.

Thay vào đó, ta tối ưu bằng cách rút gọn mảng ~cnt~ thành ~cnt[sum]~ và tính mảng này theo thứ tự tăng dần của ~pos~. Mặt khác, khi ta for tới ~pos~ và update giá trị thì ~cnt[sum]~ đang lưu giá trị của ~cnt[pos][sum]~.

Ta cần lưu thêm một vector những giá trị sẽ sử dụng của mảng ~cnt~ tại vị trí ~pos~, gọi là ~qu[pos]~.

Với mọi cặp ~(i, j)~ sao cho ~i < j~, ta có ~qu[i - 1].push_back(-(a[i] + a[j]))~ (Tương ứng với ta cần cộng kết quả cho ~cnt[i - 1][-(a[i] + a[j])]~).

Sau đó, ta lần lượt for ~i~ từ ~2~ đến ~n~ và ~j~ từ ~1~ đến ~i - 1~, cập nhật ~cnt[a[i] + a[j]] += 1~.

Dễ thấy khi đã for xong với ~i=pos~ thì mảng ~cnt[sum]~ lúc này lưu giá trị của ~cnt[pos][sum]~. Ta chỉ cần for qua những phần tử trong ~qu[i]~ (gọi là ~sum~) và cộng vào đáp án lượng ~cnt[sum]~ tương ứng.

Chú ý rằng ~sum~ có thể âm nên bạn cần shift giá trị từ đoạn ~[-2\times 10^6, 2\times 10^6]~ lên ~[0, 4\times 10^6]~ để có thể sử dụng được mảng ~cnt~. (Nghĩa là ~cnt[0]~ sẽ lưu giá trị của ~cnt[-2\times 10^6]~ ban đầu)

Độ phức tạp thời gian: Vì chỉ có ~O(N^2)~ cặp ~(i,j)~ nên tổng tất cả phần tử của ~n~ vector ~qu[]~ là ~O(N^2)~, việc update mảng ~cnt~ cũng như cộng đáp án là ~O(N^2)~. Tổng là ~O(N^2)~.

Độ phức tạp bộ nhớ: ~O(2 \times max(a[i] + a[j]) + N^2)~.