B.廢文大資料 mining
https://tioj.ck.tp.edu.tw/problems/2017
Description
給定一個序列 $a_i$ ，問有多少區間 $[l,r]$ 使得存在一個 $m \leq r$ 滿足 $\sum\limits _ {i=l}^m a_i < 0$？
Solution
先對 $a_i$ 做前綴 $s_k = \sum\limits _ {i=1}^k a_i$
對於一個固定的 $l$ 來說，題目等價於找到一個最小的 $m$ 使得 $s_m - s _ {l-1} < 0$
在 $m$ 之後的 $r$ 都會被算在答案裡面
可以用單調隊列幫每個 $i$ 找到最小的 $i’$ 使得 $s _ {i’} < s_i$ ，複雜度 $\mathcal{O}(n)$
AC code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <bits/stdc++.h>
using namespace std;
const int N = 1000025;
long long n,a[N],stk[N],p,R[N];
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) a[i] += a[i-1];
//for(int i = 0; i <= n; i++) cout << v[i] << ' '; cout << '\n';
long long sum = 0;
for(int i = n; i >= 0; i--) {
while(p && a[stk[p-1]] >= a[i]) --p;
R[i] = (p ? stk[p-1]-1 : n) - i;
stk[p++] = i;
}
for(int i = 0; i < n; i++) sum += R[i];
cout << n*(n+1)/2 - sum << '\n';
}
|