CSES - Range Updates and Sums | Cập nhật đoạn và tính tổng

Xem PDF

Điểm: 1700 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Nhiệm vụ của bạn là duy trì một mảng gồm \(n\) giá trị và xử lý hiệu quả các truy vấn sau:

  1. Tăng mỗi giá trị trong đoạn \([a, b]\) lên \(x\).
  2. Gán mỗi giá trị trong đoạn \([a, b]\) thành \(x\).
  3. Tính tổng các giá trị trong đoạn \([a,b]\).

Input

  • Dòng đầu tiên chứa hai số nguyên \(n\)\(q\) \((1 \leq n, q \leq 2 \times 10^{5})\) - kích cỡ của mảng và số lượng truy vấn.
  • Dòng tiếp theo chứa \(n\) số nguyên \(t_{1}, t_{2}, \ldots, t_{n}\) \((1 \leq t_{i} \leq 10^{6})\) - các giá trị ban đầu của mảng.
  • \(q\) dòng cuối cùng mô tả truy vấn. Định dạng của mỗi dòng là một trong các kiểu sau - \(1\) \(a\) \(b\) \(x\), \(2\) \(a\) \(b\) \(x\), hoặc \(3\) \(a\) \(b\) \((1 \leq a \leq b \leq n, 1 \leq t_{i}, x \leq 10^{6})\).

Output

  • In ra kết quả cho từng truy vấn tính tổng.

Example

Test 1

Input
6 5
2 3 1 1 5 3
3 3 5
1 2 4 2
3 3 5
2 2 4 5
3 3 5
Output
7
11
15

Bình luận

Không có bình luận nào.