Subtask 1 (~30\%~ số điểm)

Ta làm như những gì đề bài nói:

• Gọi ~V_i~ (~0 \le i < N~) là vector chứa những điểm nằm chồng lên i, ban đầu ~V_i~ chỉ chứa ~i~.
• Ta duy trì ~[L, R]~ là đoạn nằm ở dưới đáy. Ban đầu L = 0, R = n.
  • Ta duyệt lần lượt các ~X_j~ với ~1 \le j \le K~, ta tìm xem ~X_j~ hiện tại đang nằm trên vị trí nào trong vùng ~[L, R]~, bằng cách duyệt từ ~L~ đến ~R~, với mỗi vị trí thì duyệt qua các điểm nằm trong vector ở vị trí đó.
  • Sau khi tìm được vị trí đó, gọi là ~iter~, ta có 2 trường hợp:
    • TH1: ~iter - L \le R - iter~, tức phần nằm dưới đáy sẽ là từ iter -> R, ta sẽ thêm các phần tử vào các vị trí tương ứng:
      • Các điểm nằm chồng lên ~iter - 1~ thì bây giờ sẽ chồng lên ~iter + 1~
      • Các điểm nằm chòng lên ~iter - 2~ thì bây giờ sẽ chồng lên ~iter + 2~ .....
      • Các điểm nằm chồng lên ~L~ thì bây giờ sẽ chồng lên ~iter + (iter - L)~
    • TH2: ~iter - L > R - iter~, tức phần nằm dưới đáy sẽ là từ L -> iter, ta sẽ thêm các phần tử vào các vị trí tương ứng:
      • Các điểm nằm chồng lên ~iter + 1~ thì bây giờ sẽ chồng lên ~iter - 1~
      • Các điểm nằm chòng lên ~iter + 2~ thì bây giờ sẽ chồng lên ~iter - 2~ .....
      • Các điểm nằm chồng lên ~R~ thì bây giờ sẽ chồng lên ~iter + (iter - R)~

• Sau đó ta duyệt có độ dài sẽ là ~R - L + 1~, rồi từ ~L~ đến ~R~ và in ra size của từng vector

Độ phức tạp: ~O~ ~(N \times K)~

Subtask 2 (~70\%~ số điểm)

• Ta nhận thấy, khi chồng 2 chồng lên nhau, trên thực tế giống như ta gộp 2 nhóm lại, sau đó chọn ra 1 nhóm ở dưới đáy làm gốc.
• Từ đó, ta có thể sử dụng DSU, viêc gộp 2 nhóm lại bây giờ chỉ cần cập nhật lại gốc. Ví dụ, nếu ta chồng tập ~v~ lên tập ~u~, lúc này ta chỉ cần coi ~u~ làm gốc, ~v~ là con của ~u~, khi đó tất cả các con của ~v~ cũng sẽ là con của ~u~.
• Lúc này, việc tìm ~X_j~ cũng rất đơn giản, chỉ cần lấy ra gốc của vị trí ~X_j~ là xong.
• Ta cũng nhận thấy, việc các vòng for thì sẽ đều for những vị trí bị xóa đi (chồng lên tập khác), vì thế tổng độ phức tạp sẽ đúng bằng độ dài.

Độ phức tạp: ~O~ ~(N)~.