题解 P5459 【[BJOI2016]回转寿司】
GKxx
2019-07-12 23:03:08
首先对$a_i$求前缀和$s_i$
我们要求有多少对$(l,r)$，满足$L\leq s_r-s_{l-1}\leq R$
变形一下就是$s_r-R\leq s_{l-1}\leq s_r-L$
那么枚举右端点$r$，查询在这个值域范围内的数有多少个，用一个树状数组即可，查完把$s_r$加进树状数组。
一开始将所有的$s_i,s_i-L,s_i-R$混在一起离散化。
时间复杂度$O(n\log n)$
```cpp
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
template <typename T> inline void read(T& x) {
int f = 0, c = getchar(); x = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
typedef long long LL;
const int maxn = 1e5 + 307, maxsize = 3e5 + 207;
LL bit[maxsize], a[maxn], s[maxn], tmp[maxsize];
int n, L, R, all;
inline int query(int l, int r) {
int ans = 0;
for (; r; r -= r & -r) ans += bit[r];
for (--l; l; l -= l & -l) ans -= bit[l];
return ans;
}
inline void insert(int x) {
for (; x <= all; x += x & -x) ++bit[x];
}
int main() {
read(n, L, R);
tmp[++all] = 0;
for (int i = 1; i <= n; ++i) {
read(a[i]);
s[i] = s[i - 1] + a[i];
tmp[++all] = s[i];
tmp[++all] = s[i] - L;
tmp[++all] = s[i] - R;
}
std::sort(tmp + 1, tmp + all + 1);
all = std::unique(tmp + 1, tmp + all + 1) - (tmp + 1);
LL ans = 0;
insert(std::lower_bound(tmp + 1, tmp + all + 1, 0) - tmp);
for (int r = 1; r <= n; ++r) {
int x = std::lower_bound(tmp + 1, tmp + all + 1, s[r] - R) - tmp;
int y = std::lower_bound(tmp + 1, tmp + all + 1, s[r] - L) - tmp;
ans += query(x, y);
int z = std::lower_bound(tmp + 1, tmp + all + 1, s[r]) - tmp;
insert(z);
}
writeln(ans);
return 0;
}
```