离线树状数组 + 离散化 | 音符

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n, m;
set<LL> ed;
vector<LL> vec;
LL b[N], q[N];
LL tr[N];

int lowbit(int x) {
    return x & -x;
}

void add(int u, int x) {
    for (int i = u; i < N; i += lowbit(i)) tr[i] += x;
}

LL query(int u) {
    LL ans = 0;
    for (int i = u; i; i -= lowbit(i)) ans += tr[i];
    return ans;
}

int find(int x) {
    return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> b[i];

    for (int i = 0; i < m; ++i) {
        cin >> q[i];
        vec.push_back(q[i]);
    }

    LL cur = b[0];
    ed.insert(cur - 1);
    vec.push_back(cur - 1);
    for (int i = 1; i < n; ++i) {
        cur += b[i];
        ed.insert(cur - 1);
        vec.push_back(cur - 1);
    }

    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    cur = b[0];
    add(find(cur - 1), 1);
    for (int i = 1; i < n; ++i) {
        cur += b[i];
        add(find(cur - 1), 1);
    }

    for (int i = 0; i < m; ++i) {
        LL ans = query(find(q[i]));
        if (!ed.count(q[i])) ans++;
        cout << ans << '\n';
    }

    return 0;
}

贴一个非正解, 树状数组 + 离散化解法, 唐完了