Picks loves segment tree

题目描述:

现在你要维护一个长度为n的数列a。

有3种操作：1 x y t：将ax到ay中大于t的值均改为t。
2 x y t：将ax到ay均加上t。
3 x y：询问ax到ay的和。

输入格式:

第1行两个数n，m（操作个数）。
第2行n个数，第i个数为初始ai。
第3-m+2行每行一个操作（1 x y t或2 x y t或3 x y）。

输出格式:

对于每个操作2，输出一行一个整数，询问的结果。

样例输入:

6 6
2 4 5 3 7 6
2 3 4 2
3 4 6
1 2 3 5
3 3 5
3 1 2
3 5 6

样例输出:

18
17
6
13

提示:

对于30%的数据，n<=500，m<=5000，0<=ai<=50000，0<=t<=50000。

对于70%的数据，n<=10000，m<=100000，0<=ai<=50000，0<=t<=50000。

对于100%的数据，n<=500000，m<=500000，0<=ai<=2147483647，0<=t<=2147483647。

时间限制: 5000ms
空间限制: 128MB

---