Hướng dẫn cho AtCoder ABC355 D - Các đoạn giao nhau
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Sắp các đầu mút
Sắp riêng các đầu trái và đầu phải theo thứ tự tăng dần. Xét đầu trái thứ \(i\) trong thứ tự đã sắp, với \(i\) bắt đầu từ \(0\). Có \(i\) đoạn đã bắt đầu trước đoạn này. Gọi \(p\) là số đầu phải nhỏ hơn đầu trái đang xét: những đoạn đó đã kết thúc và không thể giao với đoạn mới.
Số cặp mới là \(i-p\). Các đầu phải bằng đầu trái vẫn được giữ lại vì hai đoạn đóng có điểm chung. Dùng hai con trỏ để tăng \(p\); đáp án trong C++ cần long long.
Chứng minh
Vì mỗi đoạn có đầu trái nhỏ hơn đầu phải, mọi đầu phải nhỏ hơn đầu trái đang xét đều thuộc một đoạn đã bắt đầu trước đó. Trong \(i\) đoạn trước, đúng \(p\) đoạn đã kết thúc; các đoạn còn lại chứa đầu trái này và đều giao với đoạn mới. Mỗi cặp được tính đúng một lần, khi xét đoạn xuất hiện sau trong thứ tự đầu trái. Các đoạn có cùng đầu trái được xét lần lượt và vẫn tạo đủ các cặp.
Sắp xếp tốn \(O(N\log N)\) thời gian, còn vòng quét tốn \(O(N)\). Bộ nhớ là \(O(N)\).
Bình luận