Query-Sum 2

Xem PDF

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

Cho dãy \(a\) gồm \(n\) phần tử là các số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\). Cho \(q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

  • \(1\) \(u_{i}\) \(v_{i}\) \(x_{i}\): Tăng mỗi phần tử từ vị trí \(u_{i}\) tới vị trí \(v_{i}\) lên \(x_{i}\) đơn vị.
  • \(2\) \(u_{i}\) \(v_{i}\): Tính tổng các phần tử từ vị trí \(u_{i}\) tới vị trí \(v_{i}\).

Yêu cầu: thực hiện tất cả lần lượt \(q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

  • Dòng thứ nhất gồm hai số nguyên dương \(n, q\) \((1 \leq n, q \leq 10^{5})\).
  • Dòng thứ hai gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((a_{i} \leq 10^{9})\).
  • \(q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi ba số nguyên dương \(u_{i}\), \(v_{i}\)\(x_{i}\) \((1 \leq u_{i} \leq v_{i} \leq n, 1 \leq x_{i} \leq 10^{9})\). Số \(2\) theo sau bởi hai số nguyên dương \(u_{i}\)\(v_{i}\) \((1 \leq u_{i} \leq v_{i} \leq n)\).

Output

  • Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra tổng các phần tử từ vị trí \(u\) tới vị trí \(v\) trên một dòng.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 10^{3}\).
  • Subtask \(2\) (\(30\%\) số điểm): mọi thao tác loại \(1\)\(u = v\).
  • Subtask \(3\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

Test 1

Input
5 4
1 4 6 2 3
2 1 4
1 2 5 3
1 3 4 5
2 3 5 
Output
13
30

Bình luận


  • 0
    tk22NguyenHongPhuc 2:21 p.m. 12 Tháng 2, 2024

    SOS

    1 phản hồi

    • -15
      arena89 8:24 p.m. 29 Tháng 6, 2021

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


      • -9
        Lê_Gia_Khánh 3:54 p.m. 2 Tháng 3, 2021

        Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


        • 3
          sulfuric 9:07 p.m. 4 Tháng 11, 2020

          gợi ý cho ae là bài này dùng segment tree hoặc là fenwick tree nhé

          1 phản hồi