3534. 笋尖爆炸

单点时限: 3.5 sec

内存限制: 256 MB

春天到了,在春雨过后,山上长出了许多春笋,kblack 想知道山上长了多少春笋。

我们认为山上一共有 $n$ 个笋窝,排成了一条直线,从 $1$ 开始连续编号,第 $i$ 和第 $i+1$ 个笋窝间有山路连接 ($1 \leq i \leq n - 1$)。

笋尖的生长速度非常惊人,我们称其为笋尖爆炸,可以用 $x$, $y$, $u$, $v$ 来表示。笋尖爆炸时,从 $x$ 到 $y$ 的简单路径上,依次长出以 $u$ 和 $v$ 为前两项的斐波那契数列中对应项的春笋。例如,第 $1$ 个笋窝会长出 $u$ kg 的春笋,第 $2$ 个笋窝会长出 $v$ kg 的春笋,第 $3$ 个笋窝会长出 $u+v$ kg 的春笋,而第 $4$ 个笋窝会长出 $u+2v$ kg 的春笋,以此类推。

你需要回答关于笋窝的 $m$ 个询问。

输入格式

第 $1$ 行包含 $2$ 个整数,表示笋窝数 $n$ 和询问数 $m$。($1 \leq n, m \leq 400~000$)

接下来 $m$ 行,每行的第一个整数 $op$ 表示询问的类型。

  1. 若 $op=1$,接下来 $4$ 个整数,$x$, $y$, $u$, $v$ 表示发生了一次笋尖爆炸。
  2. 若 $op=2$,接下来 $2$ 个整数,$x$, $y$,你需要输出从 $x$ 到 $y$ 简单路径上所有笋窝的春笋数量,结果对 $998244353$ 取模。

$1 \leq x, y \leq n$
$1 \leq u, v \leq 10^6$

输出格式

对于每个 $op=2$ 的询问,输出一行包含询问的结果。

样例

Input
4 4
1 1 4 2 3
2 2 4
1 2 4 4 4
2 4 1
Output
16
34

提示

在春天到来前,我们认为所有笋窝都没有春笋。

19 人解决,54 人已尝试。

24 份提交通过,共有 335 份提交。

7.0 EMB 奖励。

创建: 2 年,6 月前.

修改: 2 年,6 月前.

最后提交: 4 天,12 小时前.

来源: EOJ Monthly 2018.3

题目标签