---
tags: CP
---

# 每個人都需要一個機器貓朋友
> reference: NHDK Moon Festival Ten Point Round 2021

在 22 世紀，哆啦A夢是日本警視廳的警視總監，他奉命要調查在太平洋第7島鏈上面的勢力，進行武力分析。

哆啦A夢派出了小哆啦去調查島鏈上面的小島，共 $N$ 個小島，並且對每個小島進行武力分析，得知每個小島的武力值。

這些小島分成兩種派系，一派是支持大雄、一派是支持胖虎，哆啦A夢為了保護大雄避免胖虎的欺負，所以想先分析島鏈上有多少個區間，火拼時大雄會輸。

區間火拼：
則計算區間中大雄派的武力值總和與胖虎派武力值總和，若胖虎派武力值總和大於大雄派武力值總和則大雄派輸。


「我不在的時候你能夠好好照顧自己嗎？」哆啦 A夢邊生氣邊流淚地問大雄
# Input
只有一組資料
第一行為一個正整數 $N$ ($1 \leq N \leq 2 \cdot10^5$)，代表島鏈上面的小島數量。
第二行共有 $N$ 個整數 $a_i$ ($1 \leq |a_i| \leq 10^5$)，$|a_i|$為小島的武力值，當 $a_i > 0$ 則為大雄派 ，反之則為胖虎派。

# Output
輸出一個整數，代表島鏈上有多少個區間，火拼時大雄派會輸。

# Sample
Input1:

5
3 4 5 6 7

Output1:

0

Input2:

5
1021 -5009 1516 -8002 -6311

Output2:

13

# 範例說明

在第一個範例中，小島都是支持大雄，所以大雄沒有輸。
在第二個範例中，共有13個區間大雄會輸，分別為：
$[2, 2]$, $[4, 4]$, $[5, 5]$, $[1, 2]$
$[2, 3]$, $[3, 4]$, $[4, 5]$, $[1, 3]$
$[2, 4]$, $[3, 5]$, $[1, 4]$, $[2, 5]$, $[1, 5]$
以區間 $[1, 4]$ 為例，支持大雄的武力為$1021+1516=2537$、支持胖虎的武力為$5009+8002=13011$，所以這個區間大雄輸。
# Hint
:::spoiler
區間和可視為兩個前綴和相減。
:::

# 題解
:::spoiler
首先，本題目是在找 區間和$\leq 0$ 的個數，如果直接枚舉L與R，時間複雜度為 $O(N^3)$。
使用前綴和加速計算區間和，時間複雜度是 $O(N^2)$。

考慮到一個問題，區間和就是兩個前綴和相減，也就是尋找兩個前綴和，前面的前綴和大於後面的前綴和時，此對應的區間和就是$<0$，當我們將問題思考到這邊的時候，就完成了這題的要求。
前綴和的模反元素數量就是解。
:::

:::spoiler 解法1

#include <bits/stdc++.h>
#define pb push_back
#define Int long long
using namespace std;

Int invpair(vector<Int> &v, int l, int r) {
	if(l == r) return 0;
	int m = (l+r)/2;
	Int res = invpair(v, l, m) + invpair(v, m+1, r);
	vector<Int> tmp;
	for(int i = l, j = m+1; i <= m || j <= r; ) {
		if(i <= m && (j > r || v[i] <= v[j])) {
			tmp.pb(v[i++]);
			res += (j-m-1);
		}
		else tmp.pb(v[j++]);
	}
	for(auto it: tmp) v[l] = it, l++;
	return res;
}

void solve(){
	int n;
	cin >> n;
	vector<Int> A(n), B{0};
	for(auto& it: A) cin >> it;
	for(auto it: A) B.pb(B.back()+it); //len(B) == n+1
	Int ans = invpair(B, 0, n); //[L, R]
	cout << ans << endl;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	int t=1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

:::

:::spoiler 解法2

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define add insert
#define Int long long
#define pi acosl(-1)
#define MEM(x) memset(x,0,sizeof(x))
#define x first
#define y second
using namespace std;

struct BIT {
	vector<Int> A;
	int n;
	BIT(int _n) {
		n=_n;
		A.resize(n+1);
	}

	int lowbit(int idx) {
		return (idx&(-idx));
	}

	void update(int idx, Int v) {
		for(int i = idx+1; i <= n; i += lowbit(i)) A[i] += v;
	}

	Int query(int idx)
	{
		Int res = 0;
		for(int i = idx+1; i; i -= lowbit(i)) res += A[i];
		return res;
	}
};


void solve(){
	int n; cin >> n;
	vector<Int> A(n), B{0}, Buni;
	for(auto& it: A) cin >> it;
	for(auto it: A) B.pb(B.back() + it);
	Buni = B;
	sort(Buni.begin(), Buni.end());
	Buni.erase(unique(Buni.begin(), Buni.end()), Buni.end());


	//BIT
	BIT T1(Buni.size());
	Int ans = 0;
	for(int i = 0; i < B.size(); i++) {
		int idx = lower_bound(Buni.begin(), Buni.end(), B[i]) - Buni.begin();
		Int cnt = i - T1.query(idx);
		ans += cnt;
		T1.update(idx, 1LL);
	}
	cout << ans << endl;


}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	int t=1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

:::