MiMaTable - Min max 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: 3.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:  'c' x y w : ô (x,y) nhận giá trị mới là w

- Loại 2: 'q' x y u v: Tìm giá trị lớn nhất và nhỏ nhất trong 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ị lớn nhất và giá trị nhỏ nhất 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 2 giá trị cách nhau 1 kí tự trắng.

Ràng buộc:

q ≤ 50.000

- 50% test N ≤ 500

- 50% test N  ≤ 1.000

- Các số trong bảng ≤ 109.

Ví dụ

  • input
    4
    10 5 21 12
    7 8 19 16
    13 11 14 15
    6 9 20 18
    5
    c 1 2 5
    c 2 3 16
    q 1 2 4 4
    q 3 1 4 3
    c 1 1 15
    output
    21 5
    20 6

- Một bài tập hay để học về CTDL.

Back to Top