SumTable - Tổng trên bảng số
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: phuleethanh

    Cho bảng số kích thước N x N. Mỗi ô trong bảng có chứa một số nguyên. Có hai loại truy vấn như sau:

- Loại 1:  1 x y w : ô (x,y) tăng thêm một lượng w.

- Loại 2: 2 x y u v: Tìm tổng tất cả các ô thuộc vào hình chữ nhật con có ô trái trên là (x,y) và ô phải dưới là (u,v). (Các dòng được đánh số từ trên xuống dưới, các cột được đánh số từ trái qua phải)

    Bạn hãy lập trình giải quyết vấn đề trên. Với mỗi truy vấn loại 2 xuất ra trên một dòng giá trị tổng tìm được.

input:

-  Dòng 1 là số nguyên dương N

- N dòng sau là bảng số kích thước N x N.

- Dòng tiếp theo là số nguyên q (số lượng truy vấn)

- q dòng tiếp theo là q truy vấn (cả 2 loại).

output:

- Với mỗi truy vấn loại 2 xuất ra 1 dòng gồm 1 giá trị tổng tương ứng.

Ràng buộc:

q ≤ 100.000

- N  ≤ 1.000

- |a[i][j]| ≤ 109, |w| ≤ 109

Ví dụ

  • input
    5
    23 5 25 19 26
    31 33 7 29 15
    11 9 10 30 12
    14 27 18 16 17
    8 20 32 22 24
    10
    1 1 4 2
    1 4 1 3
    2 4 1 5 4
    2 5 3 5 3
    1 4 1 13
    1 1 2 9
    1 5 3 0
    2 4 5 5 5
    1 1 2 4
    1 1 1 -8
    output
    160
    32
    41

- Bài cơ bản, chủ yếu để các bạn học thôi nhé!

Back to Top