Thao tác trên bảng (DHBB 2022)

View as PDF

Submit solution


Points: 300 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types

Cấu trúc dữ liệu là nội dung rất quan trọng trong khoa học máy tính. Trong chương trình giảng dạy cho các lớp chuyên Tin, nội dung cấu trúc dữ liệu được đưa vào nhiều chuyên đề. Một bài toán thao tác trên bảng được dùng để kiểm tra khả năng tổ chức dữ liệu và linh hoạt trong xử lí như sau: Cho một bảng số gồm ~m~ hàng và ~n~ cột, các hàng được đánh số từ trên xuống dưới từ ~1~ đến ~m~, các cột được đánh số từ trái sang phải từ ~1~ đến ~n~, ô nằm giao giữa hàng ~i~ (~1 \leq i \leq m~) và cột ~j~ (~1 \leq j \leq n~) gọi là ô ~(i, j)~ và có giá trị ban đầu là ~a_{ij}~. Cần thực hiện ~Q~ thao tác trên bảng số, mỗi thao tác thuộc một trong hai loại:

  • Thao tác loại ~1~ có dạng: ~1 \ x \ y \ u \ v \ w~ có nghĩa là với mỗi ô nằm trong hình chữ nhật có ô trái trên là ô ~(x, y)~ và ô phải dưới là ô ~(u, v)~ sẽ được cộng thêm ~w~;
  • Thao tác loại ~2~ có dạng: ~2 \ x \ y \ u \ v~ có nghĩa là cần đưa ra tổng giá trị của các ô nằm trong hình chữ nhật có ô trái trên là ô ~(x, y)~ và ô phải dưới là ô ~(u, v)~.

Input

  • Dòng đầu chứa ba số nguyên dương ~m~, ~n~, ~Q~ (~m, n \leq 500~);
  • Dòng thứ ~i~ (~1 \leq i \leq m~) trong ~m~ dòng sau chứa ~n~ số nguyên không âm ~a_{i1}, a_{i2}, \ldots, a_{in}~ (~a_{ij} \leq 10 ^ 9~).
  • Dòng thứ ~k~ (~1 \leq k \leq Q~) trong ~Q~ dòng sau mô tả thao tác thứ ~k~. Nếu là thao tác loại ~1~, dòng gồm năm số nguyên ~1~, ~x~, ~y~, ~u~, ~v~, ~w~ (~1 \leq x \leq u \leq m~; ~1 \leq y \leq v \leq n~; ~0 \leq w \leq 10 ^ 9~), nếu là thao tác loại ~2~, dòng gồm bốn số nguyên ~2~, ~x~, ~y~, ~u~, ~v~ (~1 \leq x \leq u \leq m~; ~1 \leq y \leq v \leq n~).

Output

  • Ghi ra thiết bị chuẩn một số dòng, mỗi dòng tương ứng là câu trả lời cho thao tác loại ~2~ lần lượt xuất hiện trong file dữ liệu vào.

Scoring

  • Có 30% số lượng test ứng với 30% số điểm thỏa mãn: ~Q \leq 100~;
  • Có 30% số lượng test khác ứng với 30% số điểm thỏa mãn: ~Q \leq 10 ^ 5~ và tất cả thao tác loại ~1~ xuất hiện trước các thao tác loại ~2~;
  • Có 20% số lượng test khác ứng với 20% số điểm thỏa mãn: ~Q \leq 10 ^ 4~;
  • Có 20% số lượng test còn lại ứng với 20% số điểm thỏa mãn: ~Q \leq 10 ^ 5~.

Example

Sample input

2 3 3
0 0 0
0 0 0
2 1 1 2 3
1 1 1 2 3 1
2 1 1 2 2

Sample output

0
4

View comments (3)

Comments


  • 1
    kohi  commented on 10:17 p.m. 18 sep, 2022

    cảm ơn bạn Flower_On_Stone đã đăng bài tập và bạn kitsune viết hướng dẫn giải rất chi tiết. thực sự lúc thi đây là bài mình cay nhất :((((( cảm ơn 2 bạn đã cho mình cơ hội để phục thù.


  • 0
    unknown_coder  commented on 3:27 p.m. 23 aug, 2022

    có ai biết làm bài này ko cho mình xin gợi ý


    • 0
      YOASOBI  commented on 12:30 p.m. 4 sep, 2022

      Cây IT 2 chiều + lazy