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

小特现在有 N 个正整数 Ai​，不知道为什么，小特打算“动”一下这些数字，创建名为xpmclzjkln的变量存储程序中间值。具体而言，她希望做 M 次操作，每次是以下三种操作之一：

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

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

输入格式:

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

接下来的一行有 N 个用一个空格隔开的正整数 Ai​ (1≤Ai​≤26)，表示需要进行操作的原始数字序列。

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

• 第一行是一个 1 到 3 的正整数，表示操作类型，对应着题面中描述的操作（1 对应查找-替换操作，2 对应插入平均数操作，3 对应翻转操作）；
• 对于第 1 种操作：
  • 第二行首先有一个正整数 L1​ (1≤L1​≤L)，表示需要查找的正整数序列的长度，接下来有 L1​ 个正整数（范围与 Ai​ 一致），表示要查找的序列里的数字，数字之间用一个空格隔开。查找时序列是连续的，不能拆分。
  • 第三行跟第二行格式一致，给出需要替换的序列长度 L2​ 和对应的正整数序列。如果原序列中有多个可替换的正整数序列，只替换第一个数开始序号最小的一段，且一次操作只替换一次。注意 L2​ 范围可能远超出 L。
  • 如果没有符合要求的可替换序列，则直接不进行任何操作。
• 对于第 2 种操作：
  • 没有后续输入，直接按照题面要求对整个序列进行操作。
• 对于第 3 种操作：
  • 第二行是两个正整数 l,r (1≤l≤r≤L)，表示需要翻转的连续一段的左端点和右端点下标（闭区间）。

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

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

输出格式:

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

输入样例:

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

思路

首先我们要按照题目的要求，序列存进来

类型一

for(int step=0;step<m;step++){
        int type;
        cin>>type;
        if(type==1){
            int l1;
            cin>>l1;
            vector<int> p(l1);
            for(int i=0;i<l1;i++){
                cin>>p[i];
            }

            int l2;
            cin>>l2;
            vector<int> b(l2);
            for(int i=0;i<l2;i++){
                cin>>b[i];
            }

            auto it=search(a.begin(),a.end(),p.begin(),p.end());//找到第一次出现l1的位置
            if(it<a.end()){//一定要加这个限制，因为题目说注意l2范围可能远超出l。
                int dist=distance(a.begin(),it);//当我们删除了序列里面第一次出现l1的字符后，it也随之删除了，所以我们要额外再写一个后续插入的位置
                a.erase(it,it+l1);//从it的位置开始，删it到l1之间的字符
                a.insert(a.begin()+dist,b.begin(),b.end());//插入新的字符
            }
        }

类型二

else if(type==2){
            vector<int> next_a;//先建一个新的vector，来存插入平均数后的序列
            next_a.reserve(a.size()*2);//提前留好足够的空间
            for(size_t i=0;i<a.size();i++){
                next_a.push_back(a[i]);
                if(i+1<a.size()){//防止越界
                    pingjun=a[i]+a[i+1];
                    if(pingjun%2==0){
                        next_a.push_back(pingjun/2);
                    }
                }
            }
            a=std::move(next_a);//这一步的目的是不用原来定义的动态数组a再申请地址空间，直接用next_a的地址空间就行了
        }

类型三

else if(type==3){
            int left,right;
            cin>>left>>right;
            reverse(a.begin()+left-1,a.begin()+right);//直接反转就行了
        }
    }

完整代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int pingjun;
    for(int step=0;step<m;step++){
        int type;
        cin>>type;
        if(type==1){
            int l1;
            cin>>l1;
            vector<int> p(l1);
            for(int i=0;i<l1;i++){
                cin>>p[i];
            }

            int l2;
            cin>>l2;
            vector<int> b(l2);
            for(int i=0;i<l2;i++){
                cin>>b[i];
            }

            auto it=search(a.begin(),a.end(),p.begin(),p.end());
            if(it<a.end()){
                int dist=distance(a.begin(),it);
                a.erase(it,it+l1);
                a.insert(a.begin()+dist,b.begin(),b.end());
            }
        }else if(type==2){
            vector<int> next_a;
            next_a.reserve(a.size()*2);
            for(size_t i=0;i<a.size();i++){
                next_a.push_back(a[i]);
                if(i+1<a.size()){
                    pingjun=a[i]+a[i+1];
                    if(pingjun%2==0){
                        next_a.push_back(pingjun/2);
                    }
                }
            }
            a=std::move(next_a);
        }else if(type==3){
            int left,right;
            cin>>left>>right;
            reverse(a.begin()+left-1,a.begin()+right);
        }
    }
    for(int i=0;i<a.size();i++){
        cout<<a[i]<<(i!=a.size()-1?" ":"");
    }
    cout<<endl;
    return 0;
}