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 Fenwick hai chiều

    Cho lưới n×mn \times mn×m ban đầu toàn số 000. Xử lý qqq truy vấn:

    • 1 x y v: cộng vvv vào ô (x,y)(x, y)(x,y).
    • 2 x1 y1 x2 y2: in tổng các ô trong hình chữ nhật có góc trên-trái (x1,y1)(x_1, y_1)(x1​,y1​) và góc dưới-phải (x2,y2)(x_2, y_2)(x2​,y2​) (bao gồm biên).

    Sử dụng cây Fenwick 2D để mỗi truy vấn chạy O(log⁡nlog⁡m)O(\log n \log m)O(lognlogm).

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

      Dòng đầu chứa nnn, mmm, qqq. qqq dòng tiếp theo mô tả truy vấn theo định dạng trên.

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

      1≤n,m≤10001 \le n, m \le 10001≤n,m≤1000, 1≤q≤2⋅1051 \le q \le 2\cdot10^51≤q≤2⋅105, 1≤x,x1,x2≤n1 \le x, x_1, x_2 \le n1≤x,x1​,x2​≤n, 1≤y,y1,y2≤m1 \le y, y_1, y_2 \le m1≤y,y1​,y2​≤m, x1≤x2x_1 \le x_2x1​≤x2​, y1≤y2y_1 \le y_2y1​≤y2​, ∣v∣≤109|v| \le 10^9∣v∣≤109.

    • Đị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:

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

    Đầu ra:

    8
0

    Giải thích:

    Cộng 5 vào ô (1,1) và 3 vào ô (2,2). Hình chữ nhật (1,1)-(2,2) chứa cả hai ô nên tổng là 8. Ô (3,3) chưa được cập nhật nên tổng là 0.

    Đang tải editor...