C11SEQ - Dãy số
Tác giả: hieult
Ngôn ngữ: C++
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 100111
#define oo 1111111111
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);
using namespace std;
typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
int n,l,r;
long long a[maxn],b[maxn];
long long Search(long long x,int first,int last){
int mid;
first--;
last++;
while(first+1!=last){
mid = (last+first)/2;
if(x>a[mid])
first = mid;
else last = mid;
//if(x==5) printf("555 %d %lld %lld\n",mid,x,a[mid]);
}
return first;
}
long long mergesort(int dau,int cuoi){
int mid;
int i,j;
long long KQ = 0;
if(dau == cuoi){
if(a[dau]-a[dau-1]>=l && a[dau]-a[dau-1]<=r)
return 1;
else return 0;
}
mid = (dau+cuoi)/2;
KQ = mergesort(dau,mid)+mergesort(mid+1,cuoi);
for(i = dau;i<=mid;i++){
//if(dau==1 && mid ==2) printf("llllll %d %lld %lld %lld\n",i,a[i-1],Search(a[i-1]+r+1,mid+1,cuoi),Search(a[i-1]+l,mid+1,cuoi));
KQ += Search(a[i-1]+r+1,mid+1,cuoi)-Search(a[i-1]+l,mid+1,cuoi);
}
for(i = mid;i>=dau;i--) b[i] = a[i]; i++;
for(j =mid+1;j<=cuoi;j++) b[cuoi+mid+1-j] = a[j]; j--;
for(mid = dau; mid <= cuoi; mid++){
if (b[i]<b[j]){
a[mid]=b[i]; i++;
}
else {
a[mid]=b[j]; j--;
}
}
//printf("%d %d %d\n",dau,cuoi,KQ);
return KQ;
}
int main(){
//freopen("C11SEQ.in","r",stdin);
scanf("%d %d %d",&n,&l,&r);
//printf("%d %d %d\n",n,l,r);
a[0] = 0;
for(int i = 1;i<=n;i++)
{
scanf("%lld",&a[i]);
a[i] += a[i-1];
// printf("%d %lld\n",i,a[i]);
}
printf("%lld",mergesort(1,n));
//getch();
}