Range ReLU Query [yukicoder 877]

https://yukicoder.me/problems/no/877

前提知識

• セグメントツリーにセグメントツリーを乗せるテク

解説

https://yukicoder.me/submissions/377916

やりすぎ回答かもしれない。
maxという制約が入ったままだと問題としては扱いづらい。
なので、[l,r]という制約に加えて、x以上の数だけとってくるようにしよう。
こうすればmaxは排除できる。
sum{a[i]-x}=sum{a[i]}-x*a_cnt
であるため、A[l,r]でありx以上の数の総和と個数が分かれば問題が解ける。
これはセグメントツリーにセグメントツリーを乗せるテクを使えば実現することができる。
これにより矩形範囲のデータがとってこられるので、とってきて答える。

int N, Q, A[101010];
StaticHealthy2DSegTree sum, cnt;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];

    vector<vector<pair<int, ll>>> v_sum(N), v_cnt(N);
    rep(i, 0, N) {
        v_sum[i].push_back({A[i], 1LL*A[i]});
        v_cnt[i].push_back({A[i], 1LL});
    }
    sum.init(v_sum);
    cnt.init(v_cnt);

    rep(i, 0, Q) {
        int t, l, r, x;
        cin >> t >> l >> r >> x;
        l--;

        ll ans = sum.get(l, r, x, inf) - cnt.get(l, r, x, inf) * x;
        printf("%lld\n", ans);
    }
}