Nhận xét

• Mọi hồ phải có cá số ~0~.
• Bản thân mảng nhập vào là một hồ hợp lệ

Cách làm

Đầu tiên ta cần tạo mảng pos[] để lưu vị trí các con cá.

Ta có hai biến ~L~ và ~R~ để chỉ đoạn đang xét ~(0\le L \le R < N)~.

Cho chạy ~i~ ~(1\le i < N )~. Khi này ta có hai trường hợp:

• Nếu ~pos[i] < L~ thì ~L=pos[i]~.
• Nếu ~pos[i] > R~ thì ~R=pos[i]~.

Một hồ cá đoạn ~[L;R]~ thoả chỉ khi độ dài nó bằng ~i~ ~(1\le i < N )~. Vì ta luôn mở rộng ~L~ và ~R~ theo thứ tự tăng dần từ ~1 \to N-1~ nên ~R-L+1 = i~ thì chứng tỏ cửa sổ đang xét vừa đủ chứa các phần tử từ ~0~ đến ~R-L~.

Để dễ hiểu hơn các bạn có thể kết hợp xem bảng sau:

Độ phức tạp: ~ \mathcal{O}(n).~

Code tham khảo của lds

int pos[maxn],n,l,r;

void input()
{
    cin>>n;
    FOR(i,0,n-1)
    {
        int u;
        cin>>u;
        pos[u]=i;
    } 
}
void lds_go_goooo()
{
    l=r=pos[0];
    int ans=0,len=1;
    FOR(i,1,n-1)
    {
        if(pos[i]<l||pos[i]>r)
        {
            if(i==len)
                ans++;
            l=min(l,pos[i]) ;
            r=max(r,pos[i]);
            len=r-l+1;
        }
    }
    cout<<ans+1;  
}