Xếp hạng tần suất và độ phủ Top-k

Bối cảnh

Một luồng dữ liệu có nhiều giá trị lặp lại. Báo cáo cần xếp các giá trị theo tần suất giảm dần; nếu tần suất bằng nhau, giá trị nhỏ hơn đứng trước. Ngoài truy vấn tần suất của một giá trị x và truy vấn record ở rank k, hệ thống còn hỏi TOPSUM k: tổng số occurrence được "bao phủ" bởi k giá trị phổ biến nhất.

Ví dụ nếu frequency ranking là 10→5 lần, 20→3 lần, 30→2 lần thì TOPSUM 2 bằng 8. Để trả truy vấn này O(1), sau khi chuyển map frequency thành vector pair (count,value) và sort bằng comparator, build prefix trên count. Bài Medium kết hợp group-by, ranking và prefix trong một pipeline rõ ràng.

Ngoài việc trả ranking, TOPSUM còn cho biết mức độ tập trung của dữ liệu: vài giá trị phổ biến nhất đang chiếm bao nhiêu occurrence. Đây là loại thống kê thường gặp trong log, truy cập web hoặc dữ liệu lỗi. Vì q có thể lớn, prefix trên count phải được build một lần sau ranking thay vì cộng lại k phần tử cho mỗi truy vấn.

Yêu cầu

1. Đếm frequency bằng map.
2. Chuyển thành vector (count,value) và sort count giảm, tie value tăng.
3. Build prefix count theo ranking.
4. Xử lý FREQ x, RANK k, TOPSUM k.

Input

Dòng 1 n; dòng 2 n số; dòng q; q command.

Output

Mỗi query một dòng. RANK in value count.

Ràng buộc

1≤n,q≤5000, k hợp lệ theo số distinct.

Ví dụ 1

Input

8
5 1 5 2 1 5 2 3
7
RANK 1
RANK 2
TOPSUM 1
TOPSUM 3
FREQ 1
FREQ 4
RANK 4

Output

5 3
1 2
3
7
2
0
3 1

Giải thích

Frequency là 5→3, 1→2, 2→2, 3→1. Ranking đặt 5 ở rank1; giữa 1 và 2 cùng count2, value nhỏ hơn 1 đứng trước nên rank2 là 1, rank3 là 2. TOPSUM 1=3; TOPSUM 3=3+2+2=7. FREQ 1=2, FREQ 4=0, rank4 là 3 1.

Ví dụ 2

Input

1
7
4
RANK 1
TOPSUM 1
FREQ 7
FREQ 8

Output

7 1
1
1
0

Giải thích

Dữ liệu chỉ có một giá trị 7 và nó xuất hiện một lần, nên map frequency là 7→1. Ranking có một record (count=1,value=7) và prefix count là 0,1. Do đó RANK 1 in 7 1, TOPSUM 1 bằng 1, FREQ 7 bằng 1. Query FREQ 8 không tìm thấy key nên trả 0 mà không thay đổi map.

Thông tin học tập

• Module: M05
• Buổi: B18
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: map frequency, vector pair, custom comparator, prefix sum, lookup, top-k coverage
• Giới hạn kiến thức: B01-B18
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100