P8360 [SNOI2022] 军队

R 国的历史非常悠久。 R 国有 $n$ 个城市，国内有 $C$ 个党派，分别记为 $1,2,\dots,C$。由于 R 国的版图非常长，这 $n$ 个城市的位置可以近似为坐标轴上的 $n$ 个点。在历史的最初，记载了第 $i$ 个城市归属党派 $c_i$，城中有数量为 $a_i$ 的军队。 R 国的历史上，经常发生以下三种事件： 1. 党派 $y$ 进行了一次游说，使城市 $l$ 到城市 $r$ 的所有归属党派 $x$ 的城市全部归属了 $y$。 2. 党派 $x$ 进行了一次征兵，使城市 $l$ 到城市 $r$ 的所有归属党派 $x$ 的城市中的军队数量增加了 $v$。 3. 城市 $l$ 到城市 $r$ 之间的所有城市爆发了战争。这场战争的规模可以描述为两地之间的所有城市中的军队数量之和。注意战争不一定发生在不同党派之间，归属同一个党派的一些城市内部也可能发生内战。由于 R 国的医护系统足够先进，战争不会造成军队数量的减少。 小 N 是一个喜欢历史的女孩子，最近她想整理一下 R 国的战争史，特别是每场战争的规模。但是由于 R 国的历史实在太长了，她用纸和笔进行运算实在力不从心。于是她找到了你，希望你写一个程序，统计出 R 国历史上所有战争的规模。

无

无

**【样例 1 解释】** 最初，五个城市的军队数量分别为 $1, 2, 4, 8, 16$，归属的党派分别为 $1, 2, 3, 2, 3$。 发生的事件依次为： - 党派 $2$ 尝试在城市 $2, 3, 4$ 征兵，归属党派 $2$ 的城市 $2, 4$ 各增加了 $32$ 军队。 - 城市 $1$ 和 $4$ 之间的所有城市爆发了战争，规模为 $1 + 34 + 4 + 40 = 79$。 - 党派 $1$ 在城市 $1, 2, 3, 4, 5$ 进行了一次游说，使得原本归属党派 $3$ 的城市 $3, 5$ 归属了党派 $1$。 - 党派 $1$ 尝试在城市 $2, 3, 4, 5$ 征兵，归属党派 $1$ 的城市 $3, 5$ 各增加了 $64$ 军队。 - 城市 $2$ 和 $4$ 之间的所有城市爆发了战争，规模为 $34 + 68 + 40 = 142$。 - 党派 $3$ 尝试在城市 $1, 2, 3$ 征兵，但是党派 $3$ 现在不拥有任何城市，因此并没有成功征兵。 - 城市 $3$ 和 $5$ 之间的所有城市爆发了战争，规模为 $68 + 40 + 80 = 188$。 因此你的程序应该依次输出 $79, 142, 188$。 **【数据规模与约定】** 对于全部数据，$1 \leq n, q\leq 2.5 \times 10^5$，$1 \leq a_i, v \leq 10^8$，$1 \leq c_i, x, y \leq C$。 具体的数据规模与约定见下表。 | 测试点编号 | $n,q\leq $ | $C\leq $ | 特殊约定 | | :--------: | :---------------: | :---------------: | :----------------------------------: | | $1$ | $20$ | $20$ | | | $2$ | $50$ | $50$ | | | $3$ | $300$ | $300$ | | | $4$ | $5000$ | $5000$ | | | $5$ | $10^5$ | $10$ | | | $6$ | $1.5 \times 10^5$ | $10$ | | | $7$ | $2 \times 10^5$ | $10$ | | | $8$ | $2.5 \times 10^5$ | $10$ | | | $9$ | $1.5 \times 10^5$ | $1.5 \times 10^5$ | 对于所有操作，保证 $l=1,r=n$。 | | $10$ | $2.5 \times 10^5$ | $2.5 \times 10^5$ | 对于所有操作，保证 $l=1,r=n$。 | | $11$ | $1.5 \times 10^5$ | $1.5 \times 10^5$ | 对于所有操作 $1,2$，保证 $l=1,r=n$。 | | $12$ | $2 \times 10^5$ | $2 \times 10^5$ | 对于所有操作 $1,2$，保证 $l=1,r=n$。 | | $13$ | $2.5 \times 10^5$ | $2.5 \times 10^5$ | 对于所有操作 $1,2$，保证 $l=1,r=n$。 | | $14$ | $1.5 \times 10^5$ | $1.5 \times 10^5$ | 保证不存在操作 $1$。 | | $15$ | $2.5 \times 10^5$ | $2.5 \times 10^5$ | 保证不存在操作 $1$。 | | $16$ | $10^5$ | $10^5$ | | | $17$ | $1.5 \times 10^5$ | $1.5 \times 10^5$ | | | $18$ | $2 \times 10^5$ | $2\times 10^5$ | | | $19$ | $2.5 \times 10^5$ | $2.5 \times 10^5$ | | | $20$ | $2.5 \times 10^5$ | $2.5 \times 10^5$ | |