Editorial for Bedao Grand Contest 11 - EASYQUERY
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
bedao
Mỗi thông tin loại ~2~ đều có thể chuyển thành thông tin loại ~1~ bằng cách thực hiện ngược lại thông tin bị sai kia.
Ví dụ: thông tin thứ ~3~ yêu cầu tăng các phần tử trong đoạn [~1~, ~2~] thêm ~1~ đơn vị. Thông tin thứ ~5~ nói rằng thông tin thứ ~3~ là thông tin sai, vậy thông tin thứ ~5~ có thể chuyển thành: giảm các phần tử trong đoạn [~1~, ~2~] đi ~1~ đơn vị.
Bài toán trở thành một bài cấu trúc dữ liệu cơ bản, có thể dùng Segment Tree hoặc cây BIT để giải.
Comments