[JRKSJ R1] 吊打
题目描述
给出 $n,m$ 表示有 $n$ 个数,$m$ 次操作,$a_i$ 表示序列中第 $i$ 个数。
你需要写一种数据结构,支持两种操作:
- `1 l r`,表示将所有 $i\in[l,r]$,将 $a_i\gets\left\lfloor\sqrt{a_i}\right\rfloor$。
- `2 l r`,表示将所有 $i\in[l,r]$,将 $a_i\gets{a_i}^2$。
最后需要输出 $\sum_{i=1}^na_i$ 表示你维护了这个序列。
输入输出格式
输入格式
输入共 $m+2$ 行。\
第一行输入两个正整数 $n,m$,意义如上。\
第二行输入 $n$ 个整数 $a_i$,意义如上。\
接下来 $m$ 行,每行 $3$ 个正整数,表示一次操作,格式如上。
输出格式
输出一行一个整数表示 $\sum_{i=1}^na_i$。\
答案对 $998244353$ 取模。
输入输出样例
输入样例 #1
1 1
1
1 1 1
输出样例 #1
1
输入样例 #2
4 2
1 2 3 4
1 2 4
2 1 4
输出样例 #2
7
输入样例 #3
5 5
10 8 10 11 12
2 1 5
1 1 5
1 1 4
2 4 5
1 1 5
输出样例 #3
18
说明
对于 $5\%$ 的数据,$1\le n,m\le10$。\
对于另外 $5\%$ 的数据,保证一次 `1 l r` 操作上一步是 `2 l r`。\
对于另外 $5\%$ 的数据,保证只有 `1` 操作。\
对于另外 $5\%$ 的数据,保证只有 `2` 操作。\
对于另外 $5\%$ 的数据,保证所有的 $l=1$,$r=n$。\
对于另外 $5\%$ 的数据,$1\le n,m\le10^3$。\
对于 $100\%$ 的数据,$1\le a_i\le 10^9$,$1\le n,m\le2\times10^5$。
我们对于测试点 $7$ 至 $20$ 采用捆绑测试。
#### 样例 2 解释
| 时刻 | 序列 |
| :----------: | :----------: |
| $0$ | $[1,2,3,4]$ |
| $1$ | $[1,1,1,2]$ |
| $2$ | $[1,1,1,4]$ |