Python 暴力代码实现肥不拉几树数据结构

n = int(input())
seq = []
for _ in range(n):
    op, x, *args = map(int, input().split())
    if op == 1:
        seq.extend([1, 1] + [seq[-1] + seq[-2] for _ in range(x-2)])
    elif op == 2:
        seq = [seq[-1] + seq[-2] for _ in range(x-2)] + [1, 1] + seq
    elif op == 3:
        del seq[-x:]
    elif op == 4:
        print(max(seq[x:y+1]) % 998244353)
    elif op == 5:
        print(sum(seq[x:y+1]) % 998244353)

题目描述

SW 发明了“肥不拉几树”，但他懒得写代码了……

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

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

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

输入格式

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

输出格式

对于操作 $4,5$ 每行输出一个整数，表示查询结果。由于输出可能较大，请将输出结果 $\mod 998244353$

注意，输出结果并非为模后数值最大值，而是模前数值最大值！

样例 #1

样例输入 #1

样例输出 #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$）

对于 $40%$ 数据，保证 $x,y\leq1000,n\leq 100$

对于 $100%$ 数据，保证对于操作 $1,2,3$，保证 $0<x<\text{len}$（数列长度）。对于操作 $4,5$，保证 $0 \leq x,y< \text{len}$。数据保证 $0\leq x,y\leq1e6,0<n\leq 1e6$。