题解 P5459 【[BJOI2016]回转寿司】

· · 题解

1A

我的做法是对于每一个位置pos，用树状数组统计x \in [1, pos]内有多少个x使得\sum\limits_{i = x}^{pos}a[i]在L到R之间

先求出前缀和sum[i]

对于一个位置pos要找的数字

L \le sum[i] - val \le R

即得

val \in [sum[i] - R, sum[i] - L]

对这个前缀和离散化，方便树状数组操作

const int N = 1e5 + 10;

int n, ql, qr, ans;
int a[N], s[N];
int lsh[N], qaq;
int tree[N];

inline void add(int x, int k)
{
    for(; x <= n; x += x & -x) tree[x] += k;
}

inline int ask(int x)
{
    int res = 0;
    for(; x; x -= x & -x) res += tree[x];
    return res;
}

signed main()
{
    into();
    read(n); read(ql); read(qr);
    for(R int i = 1; i <= n; i++) read(a[i]), s[i] = s[i - 1] + a[i], lsh[i] = s[i];
    lsh[n + 1] = 0;
    sort(lsh + 1, lsh + n + 2);
    qaq = unique(lsh + 1, lsh + n + 2) - lsh - 1;
    add(lower_bound(lsh + 1, lsh + qaq + 1, 0) - lsh, 1);
    for(R int i = 1; i <= n; i++)
    {
        R int lim_l = lower_bound(lsh + 1, lsh + qaq + 1, s[i] - qr) - lsh - 1, lim_r = upper_bound(lsh + 1, lsh + qaq + 1, s[i] - ql) - lsh - 1;
        ans += ask(lim_r) - ask(lim_l);
        add(lower_bound(lsh + 1, lsh + qaq + 1, s[i]) - lsh, 1);
    }
    writeln(ans);
    return 0;
}