#PQJ934x4062. QOJ 934_4062

    ID: 3072 传统题 6000ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SNOI 2022

QOJ 934_4062

2022 年陕西省NOI 省队选拔赛试题 军队(military) 军队(military) 【题目描述】 R 国的历史非常悠久。 R 国有n 个城市,国内有C 个党派,分别记为1, 2, . . . , C。由于R 国的版图非常长,这 n 个城市的位置可以近似为坐标轴上的n 个点。在历史的最初,记载了第i 个城市归属党派ci, 城中有数量为ai 的军队。 R 国的历史上,经常发生以下三种事件:

  1. 党派y 进行了一次游说,使城市l 到城市r 的所有归属党派x 的城市全部归属了y。
  2. 党派x 进行了一次征兵,使城市l 到城市r 的所有归属党派x 的城市中的军队数量增 加了v。
  3. 城市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 页