#P18276. Shiori
Shiori
Shiori
“普通”和“平常”究竟是什么意思?手里的这把尺子,似乎也量不清楚。
企鹅 Tomorin 收藏了许多石头。为了欣赏这些石头,她在地上摆了 堆,第 堆最初有 颗石头, 是非负整数。她准备按以下指令移动石头,请你帮助处理这些操作。
1 l r v:重新摆放第 堆到第 堆石头,使每堆恰好有 颗。也就是对所有 ,令 。2 l r:Tomorin 不希望自然数出现遗漏。先计算区间当前石头数的 ,记为 ;然后从她的收藏中给区间内每一堆都增加 颗石头,即对所有 ,令 。3 l r:热心的饲养员 Rikki 想确认你有没有忽略 Tomorin,因此询问第 堆到第 堆石头的总数。输出 。
这里
$$\operatorname{mex}(S)=\min\bigl(\{0,1,2,3,\ldots\}\setminus S\bigr),$$即没有出现在集合中的最小非负整数。例如 ,。
类型 的操作只根据操作开始前的整个区间计算一次 ,随后同时更新所有元素;大于等于 的元素也必须增加 。
输入格式
第一行两个整数 (),分别表示序列长度和操作数。
第二行 个整数 (),表示初始序列。
接下来 行,每行先给出一个整数 :
- 若 ,接下来三个整数 ,满足 ,。
- 否则,接下来两个整数 ,满足 。
本题只有一个测试用例,输入开头没有测试用例数。初始值和类型 的赋值受上述上界限制,类型 操作后的值可以超过 。
输出格式
对每个类型 的操作,输出一行一个整数,表示区间和。
类型 和类型 的操作不产生输出。答案可能超过 32 位整数范围,需要使用 64 位整数。
样例输入
5 8
0 7 2 1 0
1 2 4 0
2 1 3
2 3 4
3 1 3
1 2 3 4
3 1 4
2 1 5
3 2 5
样例输出
5
11
22