# 題目
CHSH OJ c003 百鬼夜行
# 解題思路
這題很多種寫法,我記得有分治或是 BIT 的方法
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
int main(){ | |
ios::sync_with_stdio(0); | |
cin.tie(0); | |
int t; | |
cin>>t; | |
while(t--){ | |
int n,m,e; | |
multiset<int> mst; | |
cin>>n>>m>>e; | |
int limit_l=m-e,limit_r=m+e,ans=0; | |
mst.insert(0); | |
for(int i=0,sum=0,t;i<n;i++){ | |
cin>>t; | |
sum+=t; | |
auto k1=mst.upper_bound(sum-limit_l),k2=mst.lower_bound(sum-limit_r); | |
ans+=distance(k2 , k1); | |
mst.insert(sum); | |
} | |
cout<<ans<<"\n"; | |
} | |
} |