CF 1661D Progressions Covering (differential + segment tree)

Hits: 0

Topic link: click to jump

The meaning of the question: There are two sequences a and b of equal length. The a sequence starts with all 0s, and the b sequence is given by the title. Each time, you can choose a sequence of length k in a, and add 1 to the number of the range. , 2, 3…k, ask the minimum number of operations that can make ai >= bi for any i.

Idea: The last bit can only be eliminated using k, and elimination with k happens to be the fastest, so you can start processing from the back to the front, but how to update the sequence, you can use the difference to add to each modified bit Go to i (number of operations), use the [line segment tree], use the [line segment tree] to maintain the difference sequence, and the obtained prefix sum is the value of the point, which can be processed from the back to the front.

code show as below:

#include<bits/stdc++.h>
#include <ostream>

using namespace std;
typedef long long ll;
#define endl '\n'
typedef pair<int, int> PII;
#define debug() cout.flush()
#define for0(i, a) for (int i = 0; i < a; ++i)
#define REP(i, a, b)  for (int i = a; i < b; ++i)
#define FOR(i, a, b)  for (int i = a; i <= b; ++i)
#define REPC(i, a, b, c)  for (ll i = a; i < b && i < c; ++i)
#define RREP(i, a, b) for (int i = a; i >= b; --i)
const ll MOD = 1e9 + 7;
const ll mod = 998244353;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e5 + 5e3;

inline void init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int n, k;
ll sum[MAXN << 2], a[MAXN], lazy[MAXN << 2];

inline void pushup(int x) {
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
}

inline void build(int l, int r, int x) {
    if (l == r) {
        sum[x] = a[l] - a[l - 1];
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    pushup(x);
}

inline void pushdown(int l, int r, int x) {
    if (lazy[x]) {
        int mid = l + r >> 1;
        lazy[x << 1] += lazy[x];
        sum[x << 1] += (mid - l + 1) * lazy[x];
        lazy[x << 1 | 1] += lazy[x];
        sum[x << 1 | 1] += (r - mid) * lazy[x];
        lazy[x] = 0;
    }
}

inline void update(int l, int r, int x, int ql, int qr, ll val) {
    if (l >= ql && r <= qr) {
        lazy[x] += val;
        sum[x] += val * (r - l + 1);
        return;
    }
    pushdown(l, r, x);
    int mid = l + r >> 1;
    if (ql <= mid) update(l, mid, x << 1, ql, qr, val);
    if (qr > mid) update(mid + 1, r, x << 1 | 1, ql, qr, val);
    pushup(x);
}

inline ll query(int l, int r, int x, int ql, int qr) {
    int mid = l + r >> 1;
    if (l >= ql && r <= qr) {
        return sum[x];
    }
    pushdown(l, r, x);
    ll res = 0;
    if (ql <= mid) res += query(l, mid, x << 1, ql, qr);
    if (qr > mid) res += query(mid + 1, r, x << 1 | 1, ql, qr);
    return res;
}

inline void solve() {
    REP (i, 1, n + 1) {
        cin >> a[i];
    }
    ll res = 0;
    build(1, n, 1);
    RREP (i, n, 1) {
        ll num = k;
        if (i <= k) num = i;
        ll now = query(1, n, 1, 1, i);
        ll sub = max(0ll, (now + num - 1) / num);
        res += sub;
        int front = i - k + 1;
        if (front <= 0) front = 1;
        update(1, n, 1, front, i, -sub);
    }
    cout << res << endl;
}

signed main() {
    init();
    cin >> n >> k;
    solve();
    return 0;
}

You may also like...

Leave a Reply

Your email address will not be published.