不难想到，求区间和可以先 \(O(n)\) 预处理前缀和，后面就能做到对于区间 \([l,r]\) 可以 \(O(1)\) 求出 \(\sum_{i=l}^r a_i\)。接下来考虑如何求解答案。
设预处理后的前缀和数组 \(sum_i=\sum_{j=1}^i a_j\)。
区间 \([l,r]\) 满足要求，当且仅当 \(sum_r-sum_{l-1}=47\) 成立。将上述式子进行移项，可得 \(sum_{l+1}+47=sum_r\)。因此对于每一个 \(sum_i\)，我们只需统计 \(sum_i+47\) 在 \(sum\) 中的出现次数，即为符合条件的子段数量。注意，当前 \(sum_i\) 统计完后，要将其出现次数减 \(1\)（数据可能为负，避免后面重复计算）。
实现注意
-
数组要开到 \(2 \times 10^7\) 以上。
-
使用快速的输入方式（输入量很大）。
-
要开 long long。
-
多测要清空。
Code
#include <iostream>
#include <cstdio>
#include <map>
#define int long long
#define N 20000010
using namespace std;
int l,r;
int n,a[N],b[N];
int ans;
map<int,int> pd;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
signed main()
{
int T;
cin >> T;
while( T -- )
{
ans = 0;
cin >> n;
pd.clear();
for( int i = 1 ; i <= n ; i ++ )
a[i] = read(),b[i] = b[i - 1] + a[i],pd[b[i]] ++;
for( int i = 0 ; i <= n ; i ++ )
{
ans += pd[b[i] + 47];
pd[b[i]] --;
}
cout << ans << endl;
}
return 0;
}