Submission #69864215

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define int long long

using ll = long long;

const int N = 3e5 + 10;

int n;
ll a[N];
int q;

struct tree{
    ll t[4*N], ze[4*N];
    ll tag[4*N];

    void pushup(int p) {
        t[p] = min(t[p * 2], t[p * 2 + 1]);
        ze[p] = ze[p * 2] + ze[p * 2 + 1];
    }

    void pushdown(int p) {
        if (tag[p]) {
            t[p * 2] -= tag[p];
            t[p * 2 + 1] -= tag[p];
            tag[p * 2] += tag[p];
            tag[p * 2 + 1] += tag[p];
            tag[p] = 0;
        }
    }

    void build(int p, int l, int r) {
        if (l == r) {
            t[p] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(p * 2, l, mid);
        build(p * 2 + 1, mid + 1, r);
        pushup(p);
    }

    void update(int p, int l, int r, int L, int R, int k) {
        if (L <= l && r <= R) {
            tag[p] += k;
            t[p] -= k;
            return;
        }
        int mid = (l + r) / 2;
        pushdown(p);
        if (L <= mid) update(p * 2, l, mid, L, R, k);
        if (R > mid) update(p * 2 + 1, mid + 1, r, L, R, k);
        pushup(p);
    }

    pair<int, ll> query_fir(int p, int l, int r, int L, int R, int k) {
        if (t[p] >= k) {
            return {-1, -1};
        }
        if (l == r) {
            return {l, t[p]};
        }
        int mid = (l + r) / 2;
        pushdown(p);
        if (L <= mid)  {
           auto t = query_fir(p * 2, l, mid, L, R, k);
           if (t != (pair<int,ll>){-1, -1}) return t; 
        }
        if (R > mid)  {
           auto t = query_fir(p * 2 + 1, mid + 1, r, L, R, k);
           if (t != (pair<int,ll>){-1, -1}) return t; 
        }
        return {-1, -1};
    }

    void chg(int p, int l ,int r, int pos) {
        // cerr << "chg" << l << ' ' << r << ' ' << t[p] << '\n';
        if (l == r) {
            // cerr << "chggg" << l << ' ' << r << ' ' << t[p] << '\n';
            t[p] = 1e18;
            ze[p] = 1;
            return;
        }
        int mid = (l + r) / 2;
        pushdown(p);
        if (pos <= mid) chg(p * 2, l, mid, pos);
        else chg(p * 2 + 1, mid + 1, r, pos);
        pushup(p);
    }
    
    int getze(int p, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            return ze[p];
        }
        int mid = (l + r) / 2;
        pushdown(p);
        int s = 0;
        if (L <= mid) s += getze(p * 2, l, mid, L, R);
        if (R > mid) s += getze(p * 2 + 1, mid + 1, r, L, R);
        // pushup(p);
        return s;
    } 
};

tree T;


signed main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    T.build(1, 1, n);
    // cerr << T.query_fir(1, 1, n, 2, 5, 5).first << '\n';
    cin >> q;
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        // cerr << "process" << l << ' ' << r << ' ' << k << '\n';
        ll tt = r - l + 1 - T.getze(1, 1, n, l, r);
        long long s = 0;
        pair<int, ll> tp = T.query_fir(1, 1, n, l, r, k);
        while (tp != (pair<int,ll>){-1, -1}) {
            // cerr << "detect" << tp.first << ' ' << tp.second << '\n';
            s += tp.second;
            T.chg(1, 1, n, tp.first);
            tt--;
            tp = T.query_fir(1, 1, n, l, r, k);
        }
        cout << 1ll * tt * k + s << '\n';
        T.update(1, 1, n, l, r, k);
        
    }
    
    
    return 0;
}

Submission Info

Judge Result