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); } }