Kyselyt

#include <iostream>
#include <vector>
using namespace std;
 
struct SegmentTree {
    int n;
    vector<long> p, l;
    SegmentTree(int n) : n(n), p(n * 4), l(n * 4) {}
    long query(int s, int l, int r, int x, int y) {
        if (y <= l || r <= x)
            return 0;
        if (l <= x && y <= r)
            return p[s];
        push(s, y - x);
        int m = (x + y) / 2;
        return query(s * 2, l, r, x, m) + query(s * 2 + 1, l, r, m, y);
    }
    void change(int s, int l, int r, int x, int y, long k) {
        if (y <= l || r <= x)
            return;
        if (l <= x && y <= r)
            return apply(s, y - x, k);
        push(s, y - x);
        int m = (x + y) / 2;
        change(s * 2, l, r, x, m, k);
        change(s * 2 + 1, l, r, m, y, k);
        pull(s);
    }
    void push(int s, int len) {
        apply(s * 2, len / 2, l[s]);
        apply(s * 2 + 1, len / 2, l[s]);
        l[s] = 0;
    }
    void apply(int s, int len, long x) {
        p[s] += x * len;
        l[s] += x;
    }
    void pull(int s) {
        p[s] = p[s * 2] + p[s * 2 + 1];
    }
    long query(int l, int r) {
        return query(1, l, r, 0, n);
    }
    void change(int l, int r, long k) {
        change(1, l, r, 0, n, k);
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    for (auto& x : v)
        cin >> x;
    SegmentTree tree(n);
    for (int i = 0; i < n; ++i)
        tree.change(i, i + 1, -v[i]);
    vector<vector<pair<int, int>>> queries(n);
    for (int qi = 0; qi < q; ++qi) {
        int l, r;
        cin >> l >> r;
        queries[l-1].emplace_back(r, qi);
    }
    vector<long> ans(q);
    vector<int> stack{n};
    for (int i = n - 1; i >= 0; --i) {
        while (stack.back() < n && v[stack.back()] <= v[i]) {
            int sn = int(stack.size());
            tree.change(stack[sn - 1], stack[sn - 2], -v[stack[sn - 1]]);
            stack.pop_back();
        }
        tree.change(i, stack.back(), v[i]);
        stack.push_back(i);
        for (auto& [r, qi] : queries[i])
            ans[qi] = tree.query(i, r);
    }
    for (auto& u : ans)
        cout << u << '\n';
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED

Test 4

Group: 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: ACCEPTED