Phân hoạch đẹp

Xem dạng PDF
Gửi bài giải
Điểm: 3,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 2
    nai0610  đã bình luận lúc 29, Tháng 1, 2025, 19:39

    comment này spoil thuật

    đặt r[i]= j lớn nhất (i<j<=n+1) sao cho đoạn [i;j-1] thỏa mãn

    mỗi truy vấn u,v đặt u=r[u] cho đến khi u>v

    để làm điều này sử dụng nhảy nhị phân

    có thể coi r[i] là cha của i trên cây và gốc cây là n+1,sau đó dfs rồi dùng bảng thưa để xử lí việc nhảy nhị phân, tổng độ phức tạp khi trả lời truy vấn và tiền xử lí mảng r[] bằng BIT là o(nlogn+qlogn)