ORDERSET spoj – Order statistic set

Nguồn đề bài: http://vn.spoj.com/problems/ORDERSET/

1. Đề bài ORDERSET spoj

Tập hợp thứ tự

Bạn cần quản lý một tập hợp động các số, hỗ trợ hai thao tác cơ bản:

  • INSERT(S,x): nếu x không thuộc S, thêm x vào S
  • DELETE(S,x): nếu x thuộc S, xóa x khỏi S

và hai loại truy vấn

  • K-TH(S) : trả về số bé thứ k của S
  • COUNT(S,x): đếm số lượng số thuộc S bé hơn x

Dữ liệu

  • Dòng 1: Q (1 ≤ Q ≤ 200000), số thao tác
  • Q dòng sau, đầu mỗi dòng chứa ký tự I, D, K hoặc C cho biết thao tác tương ứng là INSERT, DELETE, K-TH hay COUNT. Tiếp theo là một khoảng trắng và một số nguyên là tham số cho thao tác đó.

Nếu tham số là giá trị x, dữ liệu bảo đảm 0 ≤ |x| ≤ 109. Nếu tham số là chỉ số k, dữ liệu bảo đảm 1 ≤ k ≤ 109.

Kết quả

Với mỗi truy vấn, in ra kết quả tương ứng trên một dòng. Với truy vấn K-TH, nếu k lớn hơn số phần tử của S, in ra ‘invalid’.

Ví dụ

 

2. Hướng dẫn ORDERSET spoj

Dùng segment tree.

Khởi tạo toàn bộ cây có giá trị bằng 0.

Tại mỗi lá, nếu lá đó trong S có giá trị bằng thứ tự của lá đó, ta sẽ cập nhập lá đó bằng 1, và cập nhật lại toàn bộ cây.

Khi nhập vào lệnh INSERT(S,x) , ta cập nhật lại cây.

Trong đó, pos là vị trí của lá có giá trị là b[i].

 

Khi nhập vào lệnh DELETE(S,x), ta cập nhật lại cây tương tự:

 

Khi nhập vào lệnh K-TH(S), cần phải trả về số bé thứ k, ta sử dụng chặt nhị phân để tìm:

Bởi vì có thể số phần tử trong S ít hơn k nên ta cần phải thêm vào

Khi nhập vào lệnh COUNT(S,x) – đếm số lượng số thuộc S bé hơn x, ta tính tổng tất cả các lá từ 1 tới x-1

Đó chính là kết quả.

* Bởi vì |x|<=10^9 nên không thể tạo 1 cây it với từng đấy lá.

Do Q<=200000 nên ta sử dụng phương pháp nén dữ liệu.

3. Code ORDERSET spoj C++

[/sociallocker]

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *