Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Cây phân đoạn cộng đoạn truy vấn tổng

    Cho dãy số a1,a2,…,ana_1, a_2, \dots, a_na1​,a2​,…,an​. Hãy xử lý qqq truy vấn thuộc hai loại:

    • 1 l r v: cộng giá trị vvv vào mọi phần tử aia_iai​ với l≤i≤rl \le i \le rl≤i≤r.
    • 2 l r: in ra tổng al+al+1+⋯+ara_l + a_{l+1} + \dots + a_ral​+al+1​+⋯+ar​.

    Sử dụng cây phân đoạn với lan truyền lười (lazy propagation) để đạt độ phức tạp O((n+q)log⁡n)O((n+q)\log n)O((n+q)logn).

    • Định dạng đầu vào:

      Dòng đầu chứa nnn và qqq. Dòng thứ hai chứa nnn số nguyên a1…ana_1 \dots a_na1​…an​. qqq dòng tiếp theo mô tả các truy vấn theo định dạng trên.

    • Ràng buộc đầu vào:

      1≤n,q≤2⋅1051 \le n, q \le 2\cdot10^51≤n,q≤2⋅105, ∣ai∣≤109|a_i| \le 10^9∣ai​∣≤109, ∣v∣≤109|v| \le 10^9∣v∣≤109, 1≤l≤r≤n1 \le l \le r \le n1≤l≤r≤n.

    • Định dạng đầu ra:

      Với mỗi truy vấn loại 222, in tổng tương ứng trên một dòng.

    Ví dụ:

    Đầu vào:

    5 4
1 2 3 4 5
2 1 5
1 2 4 10
2 1 5
2 2 3

    Đầu ra:

    15
45
25

    Giải thích:

    Tổng ban đầu của cả dãy là 15. Sau khi cộng 10 vào các vị trí 2..4, dãy thành [1,12,13,14,5], tổng cả dãy là 45, còn tổng a2+a3 = 12+13 = 25.

    Đang tải editor...