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 tổng và min

    Cho mảng a0,…,an−1a_0,\dots,a_{n-1}a0​,…,an−1​. Xử lý qqq truy vấn:

    • 1 p x: gán ap=xa_p = xap​=x.
    • 2 l r: in tổng các phần tử al,…,ara_l,\dots,a_ral​,…,ar​.
    • 3 l r: in giá trị nhỏ nhất trong al,…,ara_l,\dots,a_ral​,…,ar​.

    Chỉ số dựa từ 000, đoạn [l,r][l,r][l,r] bao gồm hai đầu.

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

      Dòng đầu: nnn, qqq. Dòng hai: nnn phần tử. qqq dòng truy vấn như mô tả.

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

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

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

      Mỗi truy vấn loại 2 hoặc 3 in kết quả trên một dòng.

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

    14
1
0

    Giải thích:

    Tổng cả mảng = 14. Min[1..3]=min(1,4,1)=1. Gán a2=0. Min[1..3]=min(1,0,1)=0.

    Đang tải editor...