7044: Decode
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：41
解决：10
题目描述
给你一个长度为 $n$ 的序列 $a$，共 $m$ 次操作，每次支持以下两种操作：
1 l r 对于区间 $[l,r]$ 中的每个数 $a_i$，定义一个正整数二元组 $(v,k)$ 合法，当且仅当 $\sum_{j=0}^{k-1} v+j = a_i$。对于每个 $a_i$，设所有合法二元组的 $k$ 最大值为 $x_i$，将 $a_i$ 赋值为 $x_i$。
2 l r 求区间 $[l,r]$ 的和。
1 l r 对于区间 $[l,r]$ 中的每个数 $a_i$，定义一个正整数二元组 $(v,k)$ 合法，当且仅当 $\sum_{j=0}^{k-1} v+j = a_i$。对于每个 $a_i$，设所有合法二元组的 $k$ 最大值为 $x_i$，将 $a_i$ 赋值为 $x_i$。
2 l r 求区间 $[l,r]$ 的和。
输入
输入共 $m+2$ 行。
第一行两个整数 $n,m$，含义如题所示。
第二行 $n$ 个整数，表示序列 $a$。
接下来 $m$ 行，每行一个操作，$l,r$ 均为整数。
对于 $100\%$ 的数据，$1 \leq l\le r\le n\leq 5\times 10^4$，$1\le m \le 10^5$，$1 \leq a_i \leq 10^7$。
第一行两个整数 $n,m$，含义如题所示。
第二行 $n$ 个整数，表示序列 $a$。
接下来 $m$ 行，每行一个操作，$l,r$ 均为整数。
对于 $100\%$ 的数据，$1 \leq l\le r\le n\leq 5\times 10^4$，$1\le m \le 10^5$，$1 \leq a_i \leq 10^7$。
输出
对于每个 $2$ 操作，每行输出一个整数表示答案。
样例输入 复制
3 2
1 7 6
1 1 3
2 1 3样例输出 复制
6提示
第一个操作把序列变成 $1,2,3$。
$a_1$ 的二元组是 $(1,1)$，$1=1$，$x_1=1$。
$a_2$ 的二元组是 $(3,2)$，$7=3+4$，$x_2=2$。
$a_3$ 的二元组是 $(1,3)$，$6=1+2+3$，$x_3=3$。
第二个求和操作答案就是 $1+2+3=6$。
$a_1$ 的二元组是 $(1,1)$，$1=1$，$x_1=1$。
$a_2$ 的二元组是 $(3,2)$，$7=3+4$，$x_2=2$。
$a_3$ 的二元组是 $(1,3)$，$6=1+2+3$，$x_3=3$。
第二个求和操作答案就是 $1+2+3=6$。