A6601. 「SNOI2022」军队
编程题
省选/NOI-
知识点
题目描述
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 国历史上所有战争的规模。
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 国历史上所有战争的规模。
输入格式
输入的第一行是三个正整数 $n,q,C$，分别表示城市的个数，事件的个数，和 R 国国内党派的个数。
接下来一行有 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示每个城市内初始的军队数。
接下来一行有 $n$ 个正整数 $c_1,c_2,\dots,c_n$，表示每个城市初始归属的党派。
接下来 $q$ 行，每行 $3$ 到 $5$ 个正整数，表示一次事件：
第一个正整数 $op$ 表示事件的类型。$op=1,2,3$ 分别表示「题目描述」中所述的游说，征兵和战争事件。
对于每个游说事件，接下来有 $4$ 个正整数 $l,r,x,y$，意义见「题目描述」。
对于每个征兵事件，接下来有 $4$ 个正整数 $l,r,x,v$，意义见「题目描述」。
对于每个战争事件，接下来有 $2$ 个正整数 $l,r$，意义见「题目描述」。
接下来一行有 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示每个城市内初始的军队数。
接下来一行有 $n$ 个正整数 $c_1,c_2,\dots,c_n$，表示每个城市初始归属的党派。
接下来 $q$ 行，每行 $3$ 到 $5$ 个正整数，表示一次事件：
第一个正整数 $op$ 表示事件的类型。$op=1,2,3$ 分别表示「题目描述」中所述的游说，征兵和战争事件。
对于每个游说事件，接下来有 $4$ 个正整数 $l,r,x,y$，意义见「题目描述」。
对于每个征兵事件，接下来有 $4$ 个正整数 $l,r,x,v$，意义见「题目描述」。
对于每个战争事件，接下来有 $2$ 个正整数 $l,r$，意义见「题目描述」。
输出格式
对于每个战争事件，输出一行一个整数，表示此次战争的规模。
输入输出样例
输入 #1
5 7 3 1 2 4 8 16 1 2 3 2 3 2 2 4 2 32 3 1 4 1 1 5 3 1 2 2 5 1 64 3 2 4 2 1 3 3 128 3 3 5
输出 #1
79 142 188
说明/提示
对于全部数据，$1 \le n, q, C \le 2.5 \times 10^5$，$1 \le a_i, v \le 10^8$，$1 \le c_i, x, y \le C$。
具体的数据规模与约定见下表。
| 测试点编号 | $n,q$ | $C$ | 特殊约定 |
| :--------: | :------------------: | :-------------------: | :--------------------------------------: |
| $1$ | $\le 20$ | $\le 20 $ | 无 |
| $2$ | $\le 50$ | $\le 50 $ | 无 |
| $3$ | $\le 300$ | $\le 300 $ | 无 |
| $4$ | $\le 5000$ | $\le 5000 $ | 无 |
| $5$ | $\le 10^5$ | $\le 10$ | 无 |
| $6$ | $\le 1.5\times 10^5$ | $\le 10$ | 无 |
| $7$ | $\le 2\times 10^5$ | $\le 10$ | 无 |
| $8$ | $\le 2.5\times 10^5$ | $\le 10$ | 无 |
| $9$ | $\le 1.5\times 10^5$ | $\le 1.5\times 10^5 $ | 对于所有操作，保证 $l = 1, r = n$ |
| $10$ | $\le 2.5\times 10^5$ | $\le 2.5\times 10^5 $ | 对于所有操作，保证 $l = 1, r = n$ |
| $11$ | $\le 1.5\times 10^5$ | $\le 1.5\times 10^5 $ | 对于所有操作 $1, 2$，保证 $l = 1, r = n$ |
| $12$ | $\le 2\times 10^5$ | $\le 2\times 10^5 $ | 对于所有操作 $1, 2$，保证 $l = 1, r = n$ |
| $13$ | $\le 2.5\times 10^5$ | $\le 2.5\times 10^5 $ | 对于所有操作 $1, 2$，保证 $l = 1, r = n$ |
| $14$ | $\le 1.5\times 10^5$ | $\le 1.5\times 10^5 $ | 保证不存在操作 $1$ |
| $15$ | $\le 2.5\times 10^5$ | $\le 2.5\times 10^5 $ | 保证不存在操作 $1$ |
| $16$ | $\le 10^5$ | $\le 10^5 $ | 无 |
| $17$ | $\le 1.5\times 10^5$ | $\le 1.5\times 10^5 $ | 无 |
| $18$ | $\le 2\times 10^5$ | $\le 2\times 10^5 $ | 无 |
| $19$ | $\le 2.5\times 10^5$ | $\le 2.5\times 10^5 $ | 无 |
| $20$ | $\le 2.5\times 10^5$ | $\le 2.5\times 10^5 $ | 无 |
具体的数据规模与约定见下表。
| 测试点编号 | $n,q$ | $C$ | 特殊约定 |
| :--------: | :------------------: | :-------------------: | :--------------------------------------: |
| $1$ | $\le 20$ | $\le 20 $ | 无 |
| $2$ | $\le 50$ | $\le 50 $ | 无 |
| $3$ | $\le 300$ | $\le 300 $ | 无 |
| $4$ | $\le 5000$ | $\le 5000 $ | 无 |
| $5$ | $\le 10^5$ | $\le 10$ | 无 |
| $6$ | $\le 1.5\times 10^5$ | $\le 10$ | 无 |
| $7$ | $\le 2\times 10^5$ | $\le 10$ | 无 |
| $8$ | $\le 2.5\times 10^5$ | $\le 10$ | 无 |
| $9$ | $\le 1.5\times 10^5$ | $\le 1.5\times 10^5 $ | 对于所有操作，保证 $l = 1, r = n$ |
| $10$ | $\le 2.5\times 10^5$ | $\le 2.5\times 10^5 $ | 对于所有操作，保证 $l = 1, r = n$ |
| $11$ | $\le 1.5\times 10^5$ | $\le 1.5\times 10^5 $ | 对于所有操作 $1, 2$，保证 $l = 1, r = n$ |
| $12$ | $\le 2\times 10^5$ | $\le 2\times 10^5 $ | 对于所有操作 $1, 2$，保证 $l = 1, r = n$ |
| $13$ | $\le 2.5\times 10^5$ | $\le 2.5\times 10^5 $ | 对于所有操作 $1, 2$，保证 $l = 1, r = n$ |
| $14$ | $\le 1.5\times 10^5$ | $\le 1.5\times 10^5 $ | 保证不存在操作 $1$ |
| $15$ | $\le 2.5\times 10^5$ | $\le 2.5\times 10^5 $ | 保证不存在操作 $1$ |
| $16$ | $\le 10^5$ | $\le 10^5 $ | 无 |
| $17$ | $\le 1.5\times 10^5$ | $\le 1.5\times 10^5 $ | 无 |
| $18$ | $\le 2\times 10^5$ | $\le 2\times 10^5 $ | 无 |
| $19$ | $\le 2.5\times 10^5$ | $\le 2.5\times 10^5 $ | 无 |
| $20$ | $\le 2.5\times 10^5$ | $\le 2.5\times 10^5 $ | 无 |