BIẾN ĐỔI XÂU

View as PDF

Submit solution

Points: 100.00 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C++, Pascal, Python

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.



  • 5
    bvd   commented on March 5, 2023, 4:31 p.m. edited

    Hướng làm của mình:

    Với mỗi một chữ cái, ta lưu lại tập các vị trí mà chữ cái đó xuất hiện. Ví dụ với xâu trong đề bài, ta lưu

    ~a = \{0,1,2,3\}~

    ~b = \{4,5,6,7\}~

    ~c = \{8,9,10,11\}~

    ~x = y = z = \emptyset~

    Khi đó, mỗi thao tác biến đổi xâu trở thành thao tác lấy các số trong đoạn ~[i,j]~ của tập ~c_1~ và cho vào tập ~c_2~. Dễ thấy đây là một thao tác đặc trưng của cấu trúc dữ liệu Treap, và thật vậy, khi ta biểu diễn các tập hợp trên bằng Treap thì ta có thể sử dụng các thao tác tách cây, ghép cây để thực hiện các thao tác này.

    Một số bạn sẽ lấn cấn vì Treap bình thường không hỗ trợ việc ghép tập ~x = \{1, 3, 5\}~ và tập ~y = \{2, 4, 6\}~ trong ~O(\log n)~ do các phần tử của một tập không nhỏ hơn toàn bộ các phần tử của tập kia, tuy nhiên ta có thể kết hợp kĩ thuật cập nhật lười (lazy update) với hàm ghép cây của Treap để ghép hai tập này trong ~O(\log^2 n)~. Xem chi tiết về kĩ thuật này tại Merge two cartesian trees without rule keysA < keysB