PBCSEQ SPOJ – Các đoạn nguyên

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

1. Đề bài PBCSEQ SPOJ

Mirko có một tập hợp các đoạn nguyên. Đầu tiên, anh ấy lấy ra 1 đoạn bất kì. Sau đó thực hiện lấy các đoạn khác, sao cho: đoạn lấy ra nằm trong đoạn vừa được lấy trước nó. Mirko tiếp tục cho đến khi không tìm được đoạn thoả mãn nữa.

Yêu cầu

Tìm số đoạn lớn nhất có thể lấy ra.

Dữ liệu

Dòng đầu tiên chứa số nguyên N, là số đoạn nguyên trong tập hợp.

Dòng thứ i trong số N dòng sau, chứa 2 số nguyên A,B biểu thị cho đoạn i.

Kết quả

Một số duy nhất là kết quả của bài toán.

Giới hạn

1 <= N <= 100000

1 <= A < B <= 1000000

Ví dụ

Dữ liệu
3

1 6

2 5

3 4

Kết quả

3
Dữ liệu
6

1 4

1 5

1 6

1 7

2 5

3 5

Kết quả

5

Chú ý: O(N^2) ăn được 50% số test.

2. Hướng dẫn giải PBCSEQ SPOJ

Thuật toán:sử dụng cây BIT và nén dữ liệu;Đầu tiên sắp xếp cặp điểm đầu điểm cuối giảm dần,nếu 2 cặp có điểm đầu trùng nhau thì sắp xếp tăng theo điểm cuối.Sau đó duyệt từ 1 đến n,với mỗi điểm cuối i,tìm điểm cuối j <=i với trọng số max(giả sử là gt),rồi cập nhật giá trị gt+1 vào điểm cuối i bằng cách sử dụng BIT.

mình giải thích hơi kho hiểu,có j thắc mắc các bạn để lại cmt phía dưới, mình sẽ giải đáp cho nhé

3. Code tham khảo PBCSEQ SPOJ

//saker1417
#include <bits/stdc++.h>
#define maxn 1000001
#define x first
#define y second
using namespace std;
typedef pair < int , int > II;
II e[maxn];
int n,x[maxn],sl=0;
long long bit[maxn],f[maxn];
void doc()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        e[i]=II(u,v);
        x[++sl]=u,x[++sl]=v;
    }
    sort(x+1,x+sl+1);
    int slx=0;
    for(int i=1;i<=sl;i++) if(x[i]!=x[i-1]) x[++slx]=x[i];
    sl=slx;
    for(int i=1;i<=sl;i++)
    {
        e[i].x=lower_bound(x+1,x+sl+1,e[i].x)-x;
        e[i].y=lower_bound(x+1,x+sl+1,e[i].y)-x;
    }
}
void update(int u,long long val)
{
    while(u<=sl*2)
    {
        bit[u]=max(bit[u],val);
        u+=u&(-u);
    }
}
int get(int u)
{
    long long kq=0;
    while(u)
    {
        kq=max(kq,bit[u]);
        u-=u&(-u);
    }
    return kq;
}
void tinh()
{
    int ds=0;
    for(int i=1;i<=n;i++) e[i].y=-e[i].y;
    sort(e+1,e+n+1);
    reverse(e+1,e+n+1);
    for(int i=1;i<=n;i++) e[i].y=-e[i].y;
    for(int i=1;i<=n;i++)
    {
        int saker=get(e[i].y)+1;
        update(e[i].y,saker);
        ds=max(ds,saker);
    }
    printf("%d",ds);
}
int main()
{
    ios::sync_with_stdio(false);
    doc();
    tinh();
}