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 ...
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ụ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | Dữ liệu 8 I -1 I -1 I 2 C 0 K 2 D -1 K 1 K 2 Kết quả 1 2 2 invalid |
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.
1 2 3 4 5 6 7 | r=pos[b[i]]; it[r]=1; while(r/2>0) { r/=2; it[r]=it[2*r] + it[2*r+1]; } |
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ự:
1 2 3 4 5 6 7 | r=pos[b[i]]; it[r]=0; while(r/2>0) { r/=2; it[r]=it[2*r] + it[2*r+1]; } |
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:
1 2 3 4 5 6 7 8 | lo=0, hi=q; while(hi-lo>1) { mid=(lo+hi)/2; if(a[i]<=get(1,1,q,1,mid)) hi=mid; else lo=mid; } |
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
1 2 3 4 5 | if(a[i]>get(1,1,q,1,q)) { cout<<"invalid"<<"n"; continue; } |
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++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | #include <bits/stdc++.h> using namespace std; int q, x; char s[200001]; int a[200001], b[200001], pos[200001], c[200001]; int it[1000001]; void khoitao(int r, int k, int l) { if(k==l){pos[k]=r; it[r]=0; return;} int g=(k+l)/2; khoitao(2*r,k,g); khoitao(2*r+1,g+1,l); it[r]=it[2*r]+it[2*r+1]; it[r]=0; } int get(int r, int k, int l, int u, int v) { if(v<k || u>l) return 0; if(u<=k && l<=v) return it[r]; int g=(k+l)/2; int t1=get(2*r,k,g,u,v); int t2=get(2*r+1, g+1, l, u,v); return t1+t2; } int main() { cin>>q; for(int i=1; i<=q; i++) { cin>>s[i]>>a[i]; c[i]=a[i]; } sort(c+1,c+q+1); for(int i=1; i<=q; i++) b[i]=lower_bound(c+1,c+q+1,a[i])-c; khoitao(1,1,q); for(int i=1; i<=q; i++) { if(s[i]=='I') { int r=pos[b[i]]; it[r]=1; while(r/2>0) { r/=2; it[r]=it[2*r] + it[2*r+1]; } }else if(s[i]=='D') { int r=pos[b[i]]; it[r]=0; while(r/2>0) { r/=2; it[r]=it[2*r] + it[2*r+1]; } } else if(s[i]=='K') { if(a[i]>get(1,1,q,1,q)) { cout<<"invalid"<<"n"; continue; } int lo=0, hi=q; while(hi-lo>1) { int mid=(lo+hi)/2; if(a[i]<=get(1,1,q,1,mid)) hi=mid; else lo=mid; } cout<<c[hi]<<"n"; } else cout<<get(1,1,q,1,b[i]-1)<<"n"; } } |
[/sociallocker]
