11962번: Counting Haybales

https://www.acmicpc.net/problem/11962


$O((n+q)\lg n)$

해당 구간의 건초 더미 합, 각각에 더해져야할 값, 최댓값을 가지고 세그먼트 트리를 구성한다.

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int n, q;
struct st {
    ll s, p, m;
}tree[800000];
void update(int h, int l, int r, int gl, int gr, int x) {
    if (r < gl || gr < l) return;
    if (gl <= l&&r <= gr) {
        tree[h].p += x;
        tree[h].m += x;
        return;
    }
    tree[h].s += (ll)x*(min(gr, r) - max(gl, l) + 1);
    update(h * 2 + 1, l, (l + r) / 2, gl, gr, x);
    update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    tree[h].m = min(tree[h * 2 + 1].m, tree[h * 2 + 2].m) + tree[h].p;
}
ll queryM(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return 1e18;
    if (gl <= l && r <= gr) return tree[h].m;
    return min(queryM(h * 2 + 1, l, (l + r) / 2, gl, gr), queryM(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr)) + tree[h].p;
}
ll queryS(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return 0;
    if (gl <= l && r <= gr) return tree[h].p*(r - l + 1) + tree[h].s;
    return queryS(h * 2 + 1, l, (l + r) / 2, gl, gr) + queryS(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr) + tree[h].p*(min(gr, r) - max(l, gl) + 1);
}
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        update(0, 1, n, i, i, x);
    }
    int a, b, c;
    char op;
    while (q--) {
        scanf(" %c%d%d", &op, &a, &b);
        if (op == 'M') printf("%lld\n", queryM(0, 1, n, a, b));
        else if (op == 'P') scanf("%d", &c), update(0, 1, n, a, b, c);
        else printf("%lld\n", queryS(0, 1, n, a, b));
    }
    return 0;
}