#PQJ934x4062. QOJ 934_4062
QOJ 934_4062
2022 年陕西省NOI 省队选拔赛试题 军队(military) 军队(military) 【题目描述】 R 国的历史非常悠久。 R 国有n 个城市,国内有C 个党派,分别记为1, 2, . . . , C。由于R 国的版图非常长,这 n 个城市的位置可以近似为坐标轴上的n 个点。在历史的最初,记载了第i 个城市归属党派ci, 城中有数量为ai 的军队。 R 国的历史上,经常发生以下三种事件:
- 党派y 进行了一次游说,使城市l 到城市r 的所有归属党派x 的城市全部归属了y。
- 党派x 进行了一次征兵,使城市l 到城市r 的所有归属党派x 的城市中的军队数量增 加了v。
- 城市l 到城市r 之间的所有城市爆发了战争。这场战争的规模可以描述为两地之间的所 有城市中的军队数量之和。注意战争不一定发生在不同党派之间,归属同一个党派的一些城市 内部也可能发生内战。由于R 国的医护系统足够先进,战争不会造成军队数量的减少。 小N 是一个喜欢历史的女孩子,最近她想整理一下R 国的战争史,特别是每场战争的规 模。但是由于R 国的历史实在太长了,她用纸和笔进行运算实在力不从心。于是她找到了你, 希望你写一个程序,统计出R 国历史上所有战争的规模。 【输入格式】 从文件military.in 中读入数据。 输入的第一行是三个正整数n, q, C,分别表示城市的个数,事件的个数,和R 国国内党派 的个数。 接下来一行有n 个正整数a1, a2, . . . , an,表示每个城市内初始的军队数。 接下来一行有n 个正整数c1, c2, . . . , cn,表示每个城市初始归属的党派。 接下来q 行,每行3 到5 个正整数,表示一次事件: 第一个正整数op 表示事件的类型。op = 1, 2, 3 分别表示【题目描述】中所述的游说,征兵 和战争事件。 对于每个游说事件,接下来有4 个正整数l, r, x, y,意义见【题目描述】。 对于每个征兵事件,接下来有4 个正整数l, r, x, v,意义见【题目描述】。 对于每个战争事件,接下来有2 个正整数l, r,意义见【题目描述】。 【输出格式】 输出到文件military.out 中。 对于每个战争事件,输出一行一个整数,表示此次战争的规模。 【样例输入1】 见选手目录下的military/military1.in。 第5 页,共13 页
2022 年陕西省NOI 省队选拔赛试题 军队(military) 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】 见选手目录下的military/military1.ans。 79 142 188 【样例解释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。 【样例2】 见选手目录下的military/military2.in 和military/military2.ans。 本组数据满足测试点4 的限制。 第6 页,共13 页
2022 年陕西省NOI 省队选拔赛试题 军队(military) 【样例3】 见选手目录下的military/military3.in 和military/military3.ans。 本组数据满足测试点14 的限制。 【样例4】 见选手目录下的military/military4.in 和military/military4.ans。 本组数据满足测试点18 的限制。 【数据规模与约定】 对于全部数据,1 ≤n, q, C ≤2.5 × 105,1 ≤ai, v ≤108,1 ≤ci, x, y ≤C。 具体的数据规模与约定见下表。 测试点编号 n, q C 特殊约定 1 ≤20 ≤20 无 2 ≤50 ≤50 3 ≤300 ≤300 4 ≤5000 ≤5000 5 ≤105 ≤10 6 ≤1.5 × 105 7 ≤2 × 105 8 ≤2.5 × 105 9 ≤1.5 × 105 ≤1.5 × 105 对于所有操作,保证l = 1, r = n 10 ≤2.5 × 105 ≤2.5 × 105 11 ≤1.5 × 105 ≤1.5 × 105 对于所有操作1, 2,保证l = 1, r = n 12 ≤2 × 105 ≤2 × 105 13 ≤2.5 × 105 ≤2.5 × 105 14 ≤1.5 × 105 ≤1.5 × 105 保证不存在操作1 15 ≤2.5 × 105 ≤2.5 × 105 16 ≤105 ≤105 无 17 ≤1.5 × 105 ≤1.5 × 105 18 ≤2 × 105 ≤2 × 105 19 ≤2.5 × 105 ≤2.5 × 105 20 第7 页,共13 页