Submission #69863312

---

Source Code Expand

from atcoder.lazysegtree import LazySegTree
from atcoder.fenwicktree import FenwickTree

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
queries = []
for _ in range(Q):
    l, r, k = map(int, input().split())
    l -= 1
    queries.append((l, r, k))

INF = 1 << 60
e = (INF, -1)  # 値、位置


def op(l, r):
    lv, li = l
    rv, ri = r
    if lv < rv:
        return lv, li
    else:
        return rv, ri


def mapping(f, x):
    return x[0] + f, x[1]


def composition(f, g):
    return f + g


lst = LazySegTree(op, e, mapping, composition, 0, [(a, i) for i, a in enumerate(A)])

event = [[] for _ in range(Q)]

for q, (l, r, k) in enumerate(queries):
    lst.apply(l, r, -k)
    while True:
        v, i = lst.prod(l, r)
        if v <= 0:
            event[q].append((i, v))
            lst.apply(i, i + 1, INF)
        else:
            break

ft = FenwickTree(N)
for i in range(N):
    ft.add(i, 1)

for q, (l, r, k) in enumerate(queries):
    ans = k * ft.sum(l, r)
    for i, v in event[q]:
        ans += v
        ft.add(i, -1)
    print(ans)


"""
遅延セグ木にはしったがもうちょい詰める必要がある

0になったものは忘れてよさそう

ある区間での条件を満たす要素が欲しい

なくなったタイミングをとれる？
区間更新・最小値の木　→　最小値が０以下になったらそのIDを取りつつ、タイミングと不足分を記録

fenneck木であとはとれる個数を管理　不足したときはカウントを減らす

"""

Submission Info

Judge Result