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

Download