📖 Bài giảng & lời giải: đây là Bài tập 4 trong bài giảng Bài 37: Sparse Table, Lazy trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Hàng rào có $n$ cọc, cọc thứ $i$ cao $a_i$. Có $q$ thao tác, mỗi thao tác thuộc một trong hai loại:

• 1 l r x: thay mọi cọc từ $l$ tới $r$ bằng cọc mới cao $x$ (sau thao tác, $a_l = a_{l+1} = \ldots = a_r = x$);
• 2 l r: in tổng chiều cao các cọc từ $l$ tới $r$.

Dữ liệu vào

• Dòng 1: hai số nguyên $n, q$ ($1 \le n, q \le 10^5$).
• Dòng 2: $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$).
• $q$ dòng tiếp theo, mỗi dòng là một thao tác dạng 1 l r x hoặc 2 l r ($1 \le l \le r \le n$, $0 \le x \le 10^9$).

Kết quả

Với mỗi thao tác loại 2, in kết quả trên một dòng (kết quả có thể vượt kiểu int). Dữ liệu bảo đảm có ít nhất một thao tác loại 2.

Sample Input

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

Sample Output

16
20
16