Bài 19.4. Theo Dõi Kênh Đăng Ký Hệ Thống Truyền Hình - [Độ khó: Khó]

Mô tả bài tập: Một nhà cung cấp dịch vụ truyền hình cần theo dõi các thuê bao của mình. Mỗi thuê bao (người dùng) có thể đăng ký nhiều kênh khác nhau. Tuy nhiên, một thuê bao chỉ có thể đăng ký một kênh một lần duy nhất (đăng ký lại không có tác dụng). Đồng thời, họ cũng có thể hủy đăng ký kênh. Hệ thống cần cung cấp hai thông tin quan trọng sau mỗi thao tác (đăng ký/hủy đăng ký):

1. Số lượng kênh độc nhất mà thuê bao vừa thực hiện thao tác đang đăng ký.
2. Tổng số lượng kênh độc nhất đang được ít nhất một thuê bao đăng ký trên toàn hệ thống.

Bạn sẽ được cung cấp một chuỗi các sự kiện.

INPUT FORMAT

Dòng đầu tiên chứa một số nguyên \(Q\) (\(1 \le Q \le 2 \cdot 10^5\)), là tổng số sự kiện. \(Q\) dòng tiếp theo, mỗi dòng mô tả một sự kiện theo định dạng:

• SUBSCRIBE USER_ID CHANNEL_ID: Thuê bao USER_ID đăng ký kênh CHANNEL_ID.
• UNSUBSCRIBE USER_ID CHANNEL_ID: Thuê bao USER_ID hủy đăng ký kênh CHANNEL_ID. Trong đó USER_ID và CHANNEL_ID là các số nguyên dương từ \(1\) đến \(10^9\). Giả định rằng một thuê bao không thể đăng ký một kênh đã đăng ký, và không thể hủy đăng ký một kênh chưa đăng ký. (Điều này có nghĩa là mỗi lệnh SUBSCRIBE sẽ thêm một kênh mới vào danh sách của người dùng, và mỗi lệnh UNSUBSCRIBE sẽ xóa một kênh hiện có khỏi danh sách của người dùng).

OUTPUT FORMAT

Sau mỗi sự kiện, in ra hai số nguyên trên một dòng mới, cách nhau bởi một khoảng trắng. Số thứ nhất là số kênh độc nhất mà USER_ID vừa thao tác đang đăng ký. Số thứ hai là tổng số kênh độc nhất đang được ít nhất một thuê bao đăng ký trên toàn hệ thống.

Ví dụ:

Input:

7
SUBSCRIBE 101 1
SUBSCRIBE 102 1
SUBSCRIBE 101 2
UNSUBSCRIBE 101 1
SUBSCRIBE 103 1
UNSUBSCRIBE 102 1
SUBSCRIBE 101 1

Output:

1 1
1 1
2 2
1 2
1 2
0 2
2 2

Giải thích: Để giải quyết bài toán này, ta cần theo dõi hai loại thông tin:

• Thông tin mỗi người dùng: Kênh nào họ đang đăng ký. Một std::map<int, std::set<int>> có thể được sử dụng, trong đó khóa là USER_ID và giá trị là một std::set<int> chứa các CHANNEL_ID mà người dùng đó đang đăng ký.
• Thông tin toàn hệ thống: Tổng số kênh độc nhất đang được ít nhất một thuê bao đăng ký. Điều này có thể được theo dõi bằng một std::map<int, int> để đếm số lượng người dùng đang đăng ký mỗi kênh (channel_active_users_count). Một biến global_unique_channels_count sẽ lưu trữ tổng số kênh có channel_active_users_count[CHANNEL_ID] > 0.

Cụ thể:

• Khởi tạo: global_unique_channels_count = 0.
• Khi nhận lệnh SUBSCRIBE USER_ID CHANNEL_ID:
  1. Thêm CHANNEL_ID vào user_subscriptions[USER_ID] (guaranteed thêm mới).
  2. Nếu channel_active_users_count[CHANNEL_ID] đang bằng 0, tăng global_unique_channels_count lên 1.
  3. Tăng channel_active_users_count[CHANNEL_ID] lên 1.
  4. In ra user_subscriptions[USER_ID].size() và global_unique_channels_count.
• Khi nhận lệnh UNSUBSCRIBE USER_ID CHANNEL_ID:
  1. Xóa CHANNEL_ID khỏi user_subscriptions[USER_ID] (guaranteed xóa được).
  2. Giảm channel_active_users_count[CHANNEL_ID] xuống 1.
  3. Nếu channel_active_users_count[CHANNEL_ID] trở thành 0, giảm global_unique_channels_count xuống 1.
  4. In ra user_subscriptions[USER_ID].size() và global_unique_channels_count.

Diễn giải ví dụ:

• user_subscriptions: Map (USER_ID -> set of CHANNEL_ID)
• channel_active_users_count: Map (CHANNEL_ID -> count of users subscribed)
• global_unique_channels_count: Tổng kênh độc nhất toàn hệ thống

1. SUBSCRIBE 101 1:
   • user_subscriptions[101] -> {1} (kích thước: 1)
   • channel_active_users_count[1] từ 0 -> 1. global_unique_channels_count từ 0 -> 1.
   • Output: 1 1
2. SUBSCRIBE 102 1:
   • user_subscriptions[102] -> {1} (kích thước: 1)
   • channel_active_users_count[1] từ 1 -> 2. global_unique_channels_count không đổi.
   • Output: 1 1
3. SUBSCRIBE 101 2:
   • user_subscriptions[101] từ {1} -> {1, 2} (kích thước: 2)
   • channel_active_users_count[2] từ 0 -> 1. global_unique_channels_count từ 1 -> 2.
   • Output: 2 2
4. UNSUBSCRIBE 101 1:
   • user_subscriptions[101] từ {1, 2} -> {2} (kích thước: 1)
   • channel_active_users_count[1] từ 2 -> 1. global_unique_channels_count không đổi (vì kênh 1 vẫn được 102 đăng ký).
   • Output: 1 2
5. SUBSCRIBE 103 1:
   • user_subscriptions[103] -> {1} (kích thước: 1)
   • channel_active_users_count[1] từ 1 -> 2. global_unique_channels_count không đổi.
   • Output: 1 2
6. UNSUBSCRIBE 102 1:
   • user_subscriptions[102] từ {1} -> {} (kích thước: 0)
   • channel_active_users_count[1] từ 2 -> 1. global_unique_channels_count không đổi (vì kênh 1 vẫn được 103 đăng ký).
   • Output: 0 2
7. SUBSCRIBE 101 1:
   • user_subscriptions[101] từ {2} -> {1, 2} (kích thước: 2)
   • channel_active_users_count[1] từ 1 -> 2. global_unique_channels_count không đổi.
   • Output: 2 2