Comments

• 
  

  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