#9018. 「L1-110」这不是字符串题 普及−

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Wind_Rises

题目描述

因为每年天梯赛字符串题的解答率都不尽如人意,因此出题组从几年前开始决定:每年的天梯赛的 15 分一定会有一道字符串题,另外一道则一定不是字符串题。

小特现在有 个正整数 ,不知道为什么,小特打算“动”一下这些数字,具体而言,她希望做 次操作,每次是以下三种操作之一:

  • 1.在当前正整数序列里查找给定的连续正整数序列是否存在,如存在,则将其替换成另外一个正整数序列;
  • 2.对于当前整个正整数序列,如果相邻之间的数字和为偶数,则在它们中间插入它们的平均数;
  • 3.翻转当前正整数序列指定下标之间的一段数字。这里的翻转指的是对于一段数字序列 ,将其变为

请你输出按输入顺序依次完成若干次操作后的结果。

输入格式

输入第一行是两个正整数 , (),分别表示正整数个数以及操作次数。

接下来的一行有 个用一个空格隔开的正整数 (),表示需要进行操作的原始数字序列。

紧接着有 部分,每一部分表示一次操作,你需要按照输入顺序依次执行这些操作。记 为当前操作序列长度(注意原始序列在经过数次操作后,其长度可能不再是 )。每部分的格式与约定如下:

  • 第一行是一个 的正整数,表示操作类型,对应着题面中描述的操作( 对应查找-替换操作, 对应插入平均数操作, 对应翻转操作);
  • 对于第 种操作:
    • 第二行首先有一个正整数 (),表示需要查找的正整数序列的长度,接下来有 个正整数(范围与 一致),表示要查

找的序列里的数字,数字之间用一个空格隔开。查找时序列是连续的,不能拆分。第三行跟第二行格式一致,给出需要替换的序列长度 和对应的正整数序列。

如果原序列中有多个可替换的正整数序列,只替换第一个数开始序号最小的一段,且一次操作只替换一次。注意 范围可能远超出 。如果没有符合要求的

可替换序列,则直接不进行任何操作。

  • 对于第 种操作:
    • 没有后续输入,直接按照题面要求对整个序列进行操作。
  • 对于第 种操作:
    • 第二行是两个正整数 , (),表示需要翻转的连续一段的左端点和右端点下标(闭区间)。

每次操作结束后的序列为下一次操作的起始序列。

保证操作过程中所有数字序列长度不超过 。题目中的所有下标均从 开始。

输出格式

输出进行完全部操作后的最终正整数数列,数之间用一个空格隔开,注意最后不要输出多余空格。

样例

样例输入

复制39 5
14 9 2 21 8 21 9 10 21 5 4 5 26 8 5 26 8 5 14 4 5 2 21 19 8 9 26 9 6 21 3 8 21 1 14 20 9 2 1
1
3 26 8 5
2 14 1
3
37 38
1
11 26 9 6 21 3 8 21 1 14 20 9
14 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2
3
2 40

样例输出

复制14 9 8 7 6 5 4 3 2 1 5 9 8 19 20 21 2 5 4 9 14 5 8 17 26 1 14 5 4 5 13 21 10 9 15 21 8 21 2 9 10 11 12 13 14 1 2

样例解释

为方便大家理解题意和调试程序,以下为样例每一步的中间操作序列结果: 第 1 次操作结束后:

14 9 2 21 8 21 9 10 21 5 4 5 14 1 26 8 5 14 4 5 2 21 19 8 9 26 9 6 21 3 8 21 1 14 20 9 2 1

注意这里只会替换第一次的序列。

第 2 次操作结束后:

14 9 2 21 8 21 9 10 21 5 4 5 14 1 26 8 5 14 4 5 2 21 19 8 9 26 9 6 21 3 8 21 1 14 20 9 1 2

第 3 次操作结束后:

14 9 2 21 8 21 9 10 21 5 4 5 14 1 26 8 5 14 4 5 2 21 19 8 9 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2

第 4 次操作结束后:

14 9 2 21 8 21 15 9 10 21 13 5 4 5 14 1 26 17 8 5 14 9 4 5 2 21 20 19 8 9 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2