Count Interval

题意

给定 \(n\) 个数字 \(a_1,a_2 \ldots a_n\) 和一个整数 \(k\)，求有多少个非空子段之和为 \(k\)。

也就是问有多少对数 \((l,r) (1 \leqslant l \leqslant r \leqslant n)\) 满足：$$\sum_{i=l}^{r} a_i = k$$

数据范围

• \(1 \leqslant n \leqslant 2 \times 10 ^ 5\)
• \(|A_i| \leqslant 10 ^ 9\)
• \(|K| \leqslant 10^{15}\)

思路

一看：子段和？那就考虑用前缀和优化。

一看数据范围：哦，不开long long见祖宗。

手推一下。

假设 \(sum_i\) 表示前 \(i\) 个数的和。

计算答案贡献：\(\sum_{j=1}^{i-1} sum_j=sum_i-k\)

那么问题来了，前缀和是有了，但怎样才能求出答案呢？桶是不可能的。

这时，我们就需要一个STL容器了，他就是map!

用map去记录前面每个前缀和的数量就可以轻松地A了

时间复杂度

• 时间：\(O(n\ log\ n)\)
  • 前缀和\(O(n)\)，map存储\(O(n\ log\ n)\)
• 空间：\(O(n)\)

Code

#include <iostream>
#include <vector>
#include <map>

using namespace std;
using ll = long long;

const int N = 2e5 + 10;

int n, a;
ll k, sum[N], ans;
map<ll, int> mp;

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k;
  mp[0] = 1;
  for (int i = 1; i <= n; i++) {
    cin >> a;
    sum[i] = sum[i - 1] + a;
  }
  for (int i = 1; i <= n; i++) {
    ans += mp[sum[i] - k];
    mp[sum[i]]++;
  }
  cout << ans;
  return 0;
}