Gorgeous Sequence

题目描述:

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

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

输入格式:

第1行一个数T表示接下来T组数据。

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

输出格式:

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

样例输入:

1
5 5
1 2 3 4 5
1 1 5
2 1 5
0 3 5 3
1 1 5
2 1 5

样例输出:

5
15
3
12

提示:

请用fread读入数据，fwrite输出数据

对于以data开头的数据（by qq1010903229）：

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

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

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

 

对于数据offical（官方数据），T=100，n<=200000，m<=200000，sigma(n)<=1000000，sigma(m)<=1000000，0<=ai<=2147483647，0<=t<=2147483647。

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

---

来源: HDU5306，2015 Multi-University Training Contest 2