1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 1e5;
const int MAXa = 1e5;
const int MAXsuma = MAXn * MAXa;
const int MAXlay = 36;
template <typename T>
inline void read(T &a) {
char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
read(a), read(argv...);
}
const int MAXnd = MAXn * MAXlay;
int cntnd, root, ls[MAXnd + 10], rs[MAXnd + 10];
int sum[MAXnd + 10];
inline void pushup(int id) {
sum[id] = sum[ls[id]] + sum[rs[id]];
}
void modify(int &id, int p, int le, int ri) {
if (id == 0) id = ++cntnd;
if (le == ri) {
++sum[id];
} else {
int mid = (le + ri) >> 1;
if (p <= mid) modify(ls[id], p, le, mid);
else modify(rs[id], p, mid + 1, ri);
pushup(id);
}
}
int query(int id, int l, int r, int le, int ri) {
if (id == 0) return 0;
if (le >= l && ri <= r) {
return sum[id];
} else {
int mid = (le + ri) >> 1, ans = 0;
if (l <= mid) ans += query(ls[id], l, r, le, mid);
if (r > mid) ans += query(rs[id], l, r, mid + 1, ri);
return ans;
}
}
int n, L, R;
int prefa[MAXn + 10];
int ans;
signed main() {
read(n, L, R);
for (int i = 1; i <= n; ++i) {
read(prefa[i]);
prefa[i] += prefa[i - 1];
}
for (int i = n; i; --i) {
modify(root, prefa[i], -MAXsuma, MAXsuma);
ans += query(root, L + prefa[i - 1], R + prefa[i - 1], -MAXsuma, MAXsuma);
}
printf("%lld\n", ans);
return 0;
}
|
