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;
}

Download