#P11489. [2023省队模拟]铲雪

    ID: 10637 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600提高+/省选-模逆元快速幂费马小定理指数降幂树状数组普通并查集懒标记线段树标记复合势能分析

[2023省队模拟]铲雪

题目限制

2000 ms 512 M

题目描述

一年之寄在于冬。他的冬天总是与铲雪相伴。

二十四年不间断的铲雪,已经让他和雪相敬如宾。

今年,他本打算把他故乡下北沢的雪铲个干净,全部寄到岜怷的林立高楼间去让他的学生们感受不曾感受的堆雪人,打雪仗的快乐。

但是在这之前,你需要先帮门外疯狂的食雪汉解决一道数据结构题。如果你成功了,他会给你他从上个雪天珍藏到现在的旺旺厚雪烧。

给定一个长度为 nn 的正整数序列 a1∼na_{1\sim n},你需要维护下列 mm 次操作,每次操作为下列两者其一:

0 l r\texttt{0 l r}:将 [l,r][l,r] 内所有数平方,即 ∀i∈[l,r],ai←ai2\forall i\in [l,r],a_{i}\leftarrow a_i^2。 1 l r\texttt{1 l r}:询问 [l,r][l,r] 内所有数倒数的和对 998244353998244353 取模后的结果,即求出 ∑i=lr1ai mod 998244353\sum\limits_{i=l}^r \frac 1{a_i}\bmod 998244353。

输入格式

第一行,两个整数 n,mn,m,含义见题面。

第二行 nn 个正整数 a1∼na_{1\sim n},表示初始的序列。

第 3∼m+23\sim m+2 行,每一行按照题面格式描述一个操作。

输出格式

对于每一个形如 1 l r\texttt{1 l r} 的操作,输出一行一个整数表示答案。

数据范围

对于 100%100\% 的数据:$1\le n,m\le 10^5,1\le l\le r\le n,1\le a_i\le 998244352$。

测试点编号 n,mn,m 特殊性质
1∼21\sim 2 ≤1000\le 1000 无
3∼43\sim 4 ≤14514\le 14514
5∼65\sim 6 ≤105\le 10^5 A
7∼127\sim 12 B
13∼1613\sim 16 ≤80000\le 80000 无
17∼2017\sim 20 ≤105\le 10^5

特殊性质 A:保证所有 00 操作均在 11 操作前。

特殊性质 B:保证对于所有操作,l=1,r=nl=1,r=n。

输入样例 1

5 5
2 6 8 4 3
0 2 4
1 3 4
0 3 5
0 1 5
1 1 5

输出样例 1

920256513
877299769