P12489 [集训队互测 2024] 线段树与区间加

普罗在图书馆找到了一本关于算法的书。书中介绍了一种名为“线段树”的数据结构。 > >线段树是一种有根的二叉树，其每个节点对应了序列上的一个区间 $[l,r]$，其中根节点对应 $[1,n]$。 > >对于每个节点，若其代表的序列区间 $[l,r]$ 满足 $l=r$，则其为叶节点；否则存在整数 $k(l\le k >线段树可以实现单点修改，区间修改，区间查询等操作。其中区间修改操作的实现通常需要维护名为懒惰标记的额外信息。 > 在简单了解了线段树如何维护区间加之后，普罗想要实现一个维护区间加的线段树。于是他写下了如下的代码： ```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

第一行两个整数 $n,m$，表示线段树维护的序列长度和操作次数。 接下来 $2n-1$ 行，第 $i$ 行首先是四个整数 $l_i,r_i,va_i,vb_i$，表示线段树上第 $i$ 个节点对应的区间的左端点和右端点，以及节点上的两个额外权值。如果这个节点不是根节点，那么接下来还有两个整数 $lc_i,rc_i$，表示这个节点的左儿子编号和右儿子编号。 接下来 $m$ 行，每行三个整数 $ql_i,qr_i,k_i$，表示一次区间加操作的左端点，右端点和增加的值。

在每次区间加操作后输出一行一个正整数表示 `foobar` 函数的返回值。

【数据规模与约定】 | 测试点编号 | $n,q$ | 其他约定 | | :-----------: | :-----------: | :-----------: | | $1\sim5$ | $\le2000$ | 无 | | $6\sim10$ | $\le40000$ | 无 | | $11\sim15$ | $\le2\times10^5$ | 保证存在一个线段树上的节点对应的区间为 $[ql,qr]$ | | $16\sim20$ | $\le2\times10^5$ | 保证不同的 $ql,qr$ 不超过 $200$ 种 | | $21\sim25$ | $\le2\times10^5$ | 无 | 如果测试点编号 $\bmod 5$ 为 $2$ 或 $3$，该测试点保证 $va_i=0$。 如果测试点编号 $\bmod 5$ 为 $4$ 或 $0$，该测试点保证 $vb_i=0$。 对于 $100\%$ 的数据，保证 $1\le n,q\le2\times10^5$，给出的线段树和区间加操作是合法的，$0\le va_i,vb_i,k_i