Kho hàng đa truy vấn

Bối cảnh

Một kho hàng có n sản phẩm, mỗi sản phẩm có ID duy nhất và price không âm. Sau khi dữ liệu được nạp, hệ thống phục vụ nhiều loại truy vấn mà không có cập nhật:

• FIND id: tìm price theo ID.
• ITEM k: lấy sản phẩm ở rank k khi xếp price tăng dần, tie ID tăng.
• COUNT L R: đếm bao nhiêu sản phẩm có price thuộc đoạn giá trị [L,R].
• BUDGET B: nếu mua các sản phẩm rẻ nhất trước, mua được nhiều nhất bao nhiêu sản phẩm mà tổng price không vượt B.
• RANGE L R: tổng price của các sản phẩm ở rank L..R.

Một cấu trúc duy nhất không đủ tối ưu cho mọi query. map phục vụ lookup; vector<pair<price,id>> sau sort phục vụ ranking và binary boundary theo price; prefix price phục vụ RANGE và biến BUDGET thành binary search trên prefix. Vì price không âm, prefix không giảm, tạo predicate đơn điệu. Bài Advanced yêu cầu học viên thiết kế cả pipeline, precondition và indexing; đây là dạng multi-query rất gần ICPC nhập môn.

Một chiến lược tốt là viết riêng từng helper rồi kiểm thử precondition của nó: boundary theo price chỉ đúng trên catalog đã sort; binary search BUDGET chỉ đúng vì prefix price không giảm; RANGE chỉ đúng khi rank dùng convention 1-based nhất quán. Tách các query thành những contract nhỏ giúp bài multi-query dài vẫn dễ kiểm soát và gần cách tổ chức lời giải ICPC thực tế.

Yêu cầu

1. Đọc n sản phẩm id price.
2. Build map lookup và catalog sort price tăng, tie id tăng.
3. Build prefix price.
4. Xử lý FIND/ITEM/COUNT/BUDGET/RANGE.
5. Không dùng struct/OOP.

Yêu cầu tổ chức code

Không dùng struct, pointer hay OOP; chỉ các công cụ B01–B18.

Online Judge chấm output. Giảng viên có thể review source code để xác nhận học viên dùng đúng công cụ của buổi và không vượt prerequisite.

Input

Dòng 1 n; n dòng id price; dòng q; q command.

Output

Mỗi query một dòng.

Ràng buộc

1≤n,q≤5000, ID duy nhất, 0≤price≤10^9, rank hợp lệ, L≤R.

Ví dụ 1

Input

5
10 100
20 50
30 100
40 20
50 70
8
FIND 30
ITEM 1
ITEM 4
COUNT 50 100
COUNT 21 69
BUDGET 140
RANGE 2 4
FIND 99

Output

100
40 20
10 100
4
1
3
220
NOT_FOUND

Giải thích

Catalog sau sort là (20,id40),(50,id20),(70,id50),(100,id10),(100,id30). FIND 30 trả 100; ITEM1 là 40 20, ITEM4 là 10 100. COUNT 50..100 lấy 4 sản phẩm; COUNT 21..69 chỉ có price50 nên 1. Prefix là 0,20,70,140,240,340, vì vậy BUDGET140 mua được 3 sản phẩm; RANGE2..4 bằng 50+70+100=220. ID99 không tồn tại.

Ví dụ 2

Input

1
7 42
6
FIND 7
ITEM 1
COUNT 0 41
COUNT 42 42
BUDGET 41
BUDGET 42

Output

42
7 42
0
1
0
1

Giải thích

Kho chỉ có sản phẩm id7 price42. Map FIND 7 trả 42 và ITEM 1 cũng trả 7 42. COUNT 0 41 bằng 0 vì 42 nằm ngoài đoạn, còn COUNT 42 42 bằng 1. Prefix là 0,42: với B=41, boundary cuối pre[k]≤B là k=0; với B=42, k=1. Vì vậy hai lệnh BUDGET lần lượt in 0 và 1.

Thông tin học tập

• Module: M05
• Buổi: B18
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: map lookup, vector pair, custom comparator, binary boundaries, prefix sum, binary search on prefix, multi-query pipeline
• Giới hạn kiến thức: B01-B18
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100