U81487 【模板】可持久化线段树(标准版)

题目背景

模板题,无背景

题目描述

你需要维护这样的一个长度为 n 的数组,支持如下几种操作 1、在某个历史版本上修改某一个区间上的值 2、访问某个历史版本上的某一区间的值 此外,每进行一次操作(对于操作2,即为生成一个完全一样的版本,不作任何改动),就会生成一个新的版本。版本编号即为当前操作的编号(从1开始编号,版本0表示初始状态数组)

输入格式

输入的第一行包含两个正整数n,m分别表示数组的长度和操作的个数。 第二行n个整数,为初始状态下数组各位的值 接下来m行每行包含4或5个整数,代表两种操作之一: 1、对于操作1,格式为v,l,r, value,即为在版本v的基础上,将 [l,r] 修改为 value. 2、对于操作2,格式为v, l , r,即输出版本v​中的[l,r]区间​​值的和%998244353,生成一样版本的对象应为v

输出格式

输出若干行,对应操作2的结果

说明/提示

n