P12489 [CTT Mutual Test 2024] Segment Tree and Range Add

Plo found a book about algorithms in the library. The book introduced a data structure called a “segment tree”. > > A segment tree is a rooted binary tree. Each node corresponds to an interval $[l,r]$ on a sequence, and the root corresponds to $[1,n]$. > > For each node, if its interval $[l,r]$ satisfies $l=r$, then it is a leaf node. Otherwise, there exists an integer $k(l\le k > A segment tree can support operations such as point update, range update, and range query. Implementing range updates usually requires maintaining extra information called “lazy tags”. > After learning how a segment tree maintains range add, Plo wanted to implement a segment tree that supports range add. So he wrote the following code: ```cpp #define len(i) (r[i]-l[i]+1) void push_down(int i) { a[lc[i]]+=len(lc[i])*lz[i]; lz[lc[i]]+=lz[i]; a[rc[i]]+=len(rc[i])*lz[i]; lz[rc[i]]+=lz[i]; lz[i]=0; return; } void add(int i,int ql,int qr,unsigned k) { if(qr

The first line contains two integers $n,m$, representing the sequence length maintained by the segment tree and the number of operations. The next $2n-1$ lines describe the segment tree. On line $i$, there are first four integers $l_i, r_i, va_i, vb_i$, representing the left endpoint and right endpoint of the interval corresponding to node $i$ on the segment tree, as well as the two extra weights on this node. If this node is not the root, then there are two more integers $lc_i, rc_i$, representing the indices of its left child and right child. The next $m$ lines each contain three integers $ql_i, qr_i, k_i$, representing the left endpoint, right endpoint, and the value added in one range add operation.

After each range add operation, output one line with one positive integer representing the return value of the `foobar` function.

【Scale and Conventions】 | Test Point ID | $n,q$ | Other Constraints | | :-----------: | :-----------: | :-----------: | | $1\sim5$ | $\le2000$ | None | | $6\sim10$ | $\le40000$ | None | | $11\sim15$ | $\le2\times10^5$ | It is guaranteed that there exists a node in the segment tree whose interval is $[ql,qr]$ | | $16\sim20$ | $\le2\times10^5$ | It is guaranteed that the number of distinct pairs $(ql,qr)$ does not exceed $200$ | | $21\sim25$ | $\le2\times10^5$ | None | If the test point ID $\bmod 5$ is $2$ or $3$, then for that test point it is guaranteed that $va_i=0$. If the test point ID $\bmod 5$ is $4$ or $0$, then for that test point it is guaranteed that $vb_i=0$. For $100\%$ of the data, it is guaranteed that $1\le n,q\le2\times10^5$. The given segment tree and range add operations are valid, and $0\le va_i,vb_i,k_i