QMAX spoj – Giá trị lớn nhất

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844

Nguồn đề bài: http://vn.spoj.com/problems/QMAX/

1. Đề bài QMAX spoj

Cho một dãy gồm n phần tử có giá trị ban đầu bằng 0.

Cho m phép biến đổi, mỗi phép có dạng (u, v, k): tăng mỗi phần tử từ vị trí u đến vị trí v lên k đơn vị.

Cho q câu hỏi, mỗi câu có dạng (u, v): cho biết phần tử có giá trị lớn nhất thuộc đoạn [u, v]

Giới hạn

  • n, m, q <= 50000
  • k > 0
  • Giá trị của một phần tử luôn không vượt quá 231-1

Input

  • Dòng 1: n, m
  • m dòng tiếp theo, mỗi dòng chứa u, v, k cho biết một phép biến đổi
  • Dòng thứ m+2: p
  • p dòng tiếp theo, mỗi dòng chứa u, v cho biết một phép biến đổi

Output

  • Gồm p dòng chứa kết quả tương ứng cho từng câu hỏi.

Example

2. Hướng dẫn QMAX spoj

– xử lí phần truy vấn giống như bài MTHCN bạn có thể tham khảo tại đây: https://kienthuc24h.com/2015/01/11/mthcn-spoj-hinh-chu-nhat-ki-la/

– sau đó dùng cây Interval Tree để giải quyết 😀

3. code tham khảo QMAX spoj (pascal, C++)

Pascal

c++

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *