肥不拉几树

题目描述

您需要写一种数据结构来维护一个数列，其中需要提供以下操作：

1. 在数列后方插入 $F_1 \cdots F_x$（斐波那契数列：$1,1,2,3,5,8\cdots$）
2. 在数列前方插入 $F_1 \cdots F_x$
3. 在数列后方删去 $x$ 个数
4. 查询数列区间 $[x,y]$ 的最大值
5. 查询数列区间 $[x,y]$ 的和

数列一开始为空，删除操作与查询操作保证数列内有足够的数

输入格式

第一行为 $n$，表示操作的个数，下面 $n$ 行每行，对于操作 $1,2,3$ 有两个数 `op` 和 $x$，对于操作 $4,5$ 有三个数 `op`,$x$ 和 $y$，`op` 表示操作的序号（$1 \leq `opt` \leq 6 $)

输出格式

对于操作 $4,5$ 每行输出一个数，表示查询结果

样例 #1

样例输入 #1

6
1 5
3 2
4 1 2
1 3
2 2
5 3 5

样例输出 #1

2
4

提示

以下是每个操作后数列的内容：

• $1,1,2,3,5$
• $1,1,2$
• $1,1,2$（查询 $[1,2]$ 的最大值结果为 $2$）
• $1,1,2,1,1,2$
• $1,1,1,1,2,1,1,2$
• $1,1,1,1,2,1,1,2$（查询 $[3,5]$ 的和结果为 $4$）

数据生成器

以下是用于生成该题输入数据的C++代码：

#include <iostream>
#include <vector>

using namespace std;

// 定义斐波那契数列生成函数
vector<int> generateFibonacciSequence(int n) {
    vector<int> fib(n);
    fib[0] = 1;
    fib[1] = 1;
    for (int i = 2; i < n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    return fib;
}

int main() {
    int n;
    cin >> n;

    vector<int> sequence;
    vector<int> fib = generateFibonacciSequence(30);  // 生成前30个斐波那契数

    for (int i = 0; i < n; i++) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            cin >> x;
            for (int j = 0; j < x; j++) {
                sequence.push_back(fib[j]);
            }
        } else if (op == 2) {
            int x;
            cin >> x;
            for (int j = x-1; j >= 0; j--) {
                sequence.insert(sequence.begin(), fib[j]);
            }
        } else if (op == 3) {
            int x;
            cin >> x;
            for (int j = 0; j < x; j++) {
                sequence.pop_back();
            }
        } else if (op == 4) {
            int x, y;
            cin >> x >> y;
            int maxVal = sequence[x-1];
            for (int j = x; j < y; j++) {
                maxVal = max(maxVal, sequence[j]);
            }
            cout << maxVal << endl;
        } else if (op == 5) {
            int x, y;
            cin >> x >> y;
            int sum = 0;
            for (int j = x-1; j < y; j++) {
                sum += sequence[j];
            }
            cout << sum << endl;
        }
    }

    return 0;
}

你可以使用该代码生成输入数据，并将其保存到一个文件中，然后使用你的程序对该文件进行对拍测试。注意，代码中生成斐波那契数列的部分可以自行调整，以满足对拍的需要。