C11SEQ - Dãy số
Tác giả: RR
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <complex>
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back
using namespace std;
//Buffer reading
int INP,AM;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
if(!*inp) { \
if (feof(stdin)) memset(BUF, 0, sizeof BUF); else fread(BUF,1,BUFSIZE,stdin); \
inp=BUF; \
} \
INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
AM=0;\
GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
if (INP=='-') {AM=1;GETCHAR(INP);} \
j=INP-'0'; GETCHAR(INP); \
while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
if (AM) j=-j;\
}
//End of buffer reading
const int MN = 100111;
int n, s;
long long a[MN], c[MN], l, r;
long long bit[MN];
#define _(x) ((x) & (-(x)))
void update(int x) {
while (x <= 100000) {
bit[x] ++;
x += _(x);
}
}
long long get(int x) {
if (x < 0) return 0;
long long res = 0;
while (x) {
res += bit[x];
x -= _(x);
}
return res;
}
void RR() {
FOR(i,1,n) c[i] = a[i];
sort(c+1, c+n+1);
s = unique(c+1, c+n+1) - c - 1;
FOR(i,1,n) a[i] = lower_bound(c+1, c+s+1, a[i]) - c;
++s; c[s] = 1000111000111000111LL;
}
long long cal(long long x) {
memset(bit, 0, sizeof bit);
long long res = 0;
FORD(i,n,0) {
int u = upper_bound(c+1, c+s+1, c[a[i]] + x) - c - 1;
res += get(u);
if (i) update(a[i]);
}
return res;
}
int main() {
GN(n); GN(l); GN(r); FOR(i,1,n) GN(a[i]);
FOR(i,1,n) a[i] += a[i-1];
RR();
cout << cal(r) - cal(l-1) << endl;
return 0;
}