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| ≤ 10⁹. Nếu tham số là chỉ số k, dữ liệu bảo đảm 1 ≤ k ≤ 10⁹.

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ụ

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.

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ự:

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:

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

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++

#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]

ORDERSET spoj – Order statistic set