P3924 Kanna's Segment Tree

Kobayashi is a programmer, and naturally Kanna becomes very interested in this human “magic,” so Kobayashi starts teaching her OI.  Today Kanna learned a magical structure called a segment tree, which can maintain information over an interval and is very powerful. Kanna tried to write a segment tree that maintains the sum over intervals. Since she doesn’t know how to use lazy propagation, she performs each range add operation by brute-force point updates. The specific code is as follows: ```cpp struct Segment_Tree{ #define lson (o

The first line contains integers $n, m, qwq$, which denote the length of the original sequence, the number of operations, and the denominator used for output. The second line contains $n$ integers, the original sequence. The next $m$ lines each contain three integers $l, r, x$, meaning add $x$ to the interval $[l, r]$.

Output $m$ lines. Each line is the expected path-sum value multiplied by $qwq$.

Constraints: - For 30% of the testdata, $1 \leq n, m \leq 100$. - For 70% of the testdata, $1 \leq n, m \leq 10^{5}$. - For 100% of the testdata, $1 \leq n, m \leq 10^{6}$. - $-1000 \leq a_i, x \leq 1000$. Translated by ChatGPT 5