Migrated from Lutece 3138 QHJ全家桶

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：吉司机线段树

为了对标某著名产品，QHJ最近新开了一家QHJ快餐店，你受宣传吸引前去点了一份QHJ全家桶。

很不幸，结账时你发现身上并没有足够的钱来支付账单（黑心老板QHJ石锤）。

但好消息是，QHJ决定给你出一道题，如果你能正确地回答出来，就可以请你免费享用这份QHJ全家桶。

刚开始，QHJ给了你一个长度为 $n$ 的序列 $\{a_n\}$ ，他一共会对该序列进行 $m$ 次操作，每次操作形如：

• 1 l r k，对于所有的 $i\in[l,r]$ ，将 $a_i$ 的值变为 $a_i+k$ 。
• 2 l r x，对于所有的 $i\in[l,r]$ ，将 $a_i$ 的值变为 $\max(a_i,x)$ 。
• 3 l r，询问 $\sum_{i=l}^r a_i$ 的结果。
• 4 l r，令 $f(i)$ 表示在上述修改操作中 $a_i$ 的值的变化次数，询问 $\sum_{i=l}^r f(i)$ 的结果。
• 5 l r，令集合 $S_i$ 表示在上述修改操作中 $a_i$ 曾表示过的所有的数， $g_i$ 为 $S_i$ 中最大的数，询问 $\max_{l\le i\le r} g_i$ 的结果。
• 6 l r，令集合 $S_i$ 表示在上述修改操作中 $a_i$ 曾表示过的所有的数， $h_i$ 为 $S_i$ 中最小的数，询问 $\min_{l\le i\le r} h_i$ 的结果。

Input

输入的第一行包括两个正整数 $n,m$ ，分别表示序列的长度以及操作的个数。

接下来的一行共 $n$ 个整数，表示序列 $\{a_n\}$ 。

接下来的 $m$ 行每行一个操作，格式和意义如题面所述。

Output

对于每个询问类型的操作，输出一行一个整数表示答案。

Samples

6 9
1 2 3 4 5 6
3 2 4
1 3 6 -2
5 4 6
2 3 4 5
1 4 4 1
6 4 5
2 4 6 4
4 1 6
3 1 6

9
6
2
8
22

Constraints

$1\le n,m\le 2\times 10^5,1\le a_i,x\le n,1\le l\le r\le n,0<|k|\le n$

Resources

2024 UESTC ICPC Training for Data Structures