VP的时候以为会有负数 我也是神人了
查看原帖
VP的时候以为会有负数 我也是神人了
817442
Sakuya_maid楼主2025/6/26 18:32

在有负数的情况下,如何快速统计先前的合法区间?

把全部前缀丢到权值线段树上即可 ,记得先离线后离散

int n, m, k;
int a[N];
int pre[N];
int ans;

void Sakuya()
{
    cin >> n >> k;
    vector<int>b;
    b.emplace_back(0);
    for(int i = 1; i <= n; ++ i){
        cin >> a[i];

        pre[i] = pre[i - 1] + a[i];
        
        b.emplace_back(pre[i]);
    }

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

    auto get = [&](int x) -> int{
        return lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
    };

    int siz = b.size() + 5;

    vector<int>tr(siz * 4 + 5);

    auto pushup = [&](int x, int y) -> int{
        return x + y;
    };

    auto update = [&](auto self, int u, int l, int r, int pos) -> void{
        if(l == r){
            tr[u] += 1;
            return;
        }
        if(pos <= mid)self(self, u << 1, l, mid, pos);
        else self(self, u << 1 | 1, mid + 1, r, pos);
        tr[u] = pushup(tr[u << 1], tr[u << 1 | 1]);
    };

    auto query = [&](auto self, int u, int l, int r, int x, int y) -> int{
        if(x <= l && y >= r){
            return tr[u];
        }
        int res = 0;
        if(x <= mid)res += self(self, u << 1, l, mid, x, y);
        if(y > mid)res += self(self, u << 1 | 1, mid + 1, r, x, y);
        return res;
    };

    // for(auto i : b)cout << i << " ";
    // cout << "\n";

    auto now = get(0);
    update(update, 1, 1, siz, now);

    for(int i = 1; i <= n; ++ i){
        auto now = get(pre[i]);
        update(update, 1, 1, siz, now);

        auto need = pre[i] - k;
        
        int l = 0, r = b.size() - 1, pos = -1;
        while(l <= r){
            if(b[mid] <= need){
                pos = mid;
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }

        if(pos != -1)
        ans += query(query, 1, 1, siz, 1, pos + 1);
    }

    cout << ans << "\n";
}
2025/6/26 18:32
加载中...