C11SEQ - Dãy số
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int n,f[100100];
long long re,L,R,a[100100];
vector <long long> X;
void add(int x)
{
x++;
while (x<=int(X.size())) f[x]++, x+=x&-x;
}
int get(int x)
{
int r=0;
x++;
while (x) r+=f[x],x-=x&-x;
return r;
}
int main()
{
int x;
cin >> n >> L >> R;
X.push_back(0);
for (int i=1;i<=n;i++)
{
scanf("%d",&x);
a[i]=a[i-1]+x;
X.push_back(a[i]);
}
sort(X.begin(),X.end());
X.resize(unique(X.begin(),X.end())-X.begin());
for (int i=0;i<=n;i++)
{
if (i)
{
int low=lower_bound(X.begin(),X.end(),a[i]-R)-X.begin();
int high=upper_bound(X.begin(),X.end(),a[i]-L)-X.begin();
if (low<high) re+=get(high-1)-get(low-1);
}
x=lower_bound(X.begin(),X.end(),a[i])-X.begin();
add(x);
}
cout << re << endl;
return 0;
}