Đề bài

Với một mảng số nguyên \(a[0],a[1],\ldots,a[m-1]\), gọi vẻ đẹp của mảng là số lượng số nguyên dương \(k\) sao cho có thể chia mảng thành \(k\) mảng con rời nhau, mỗi mảng con là một dãy phần tử liên tiếp, mỗi phần tử của mảng ban đầu thuộc đúng một mảng con, và tất cả các mảng con đều có cùng số nguyên dương nhỏ nhất không xuất hiện.

Số nguyên dương nhỏ nhất không xuất hiện của một mảng là số nguyên nhỏ nhất lớn hơn \(0\) không xuất hiện trong mảng đó.

Cho mảng số nguyên \(v[0],v[1],\ldots,v[n-1]\) và \(q\) truy vấn \((l_i,r_i)\), trong đó \(0\le l_i\le r_i<n\). Với mỗi truy vấn, hãy tìm vẻ đẹp của mảng

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

std::vector<int> solve(
    int n,
    std::vector<int>& v,
    int q,
    std::vector<std::pair<int, int>>& queries
);

• n: kích thước của mảng số nguyên.
• v: mảng ban đầu có độ dài \(n\).
• q: số truy vấn.
• queries: mảng độ dài \(q\) mô tả các truy vấn; phần tử thứ \(i\) là cặp \((l_i,r_i)\).
• Trong giao diện của thí sinh, mọi chỉ số trong queries đều bắt đầu từ \(0\). Dữ liệu kiểm thử thô chính thức lưu hai đầu mút bắt đầu từ \(1\); trình chấm chuyển chúng về chỉ số bắt đầu từ \(0\) trước khi gọi solve.
• Hàm phải trả về một mảng gồm \(q\) số nguyên, lần lượt là đáp án của các truy vấn.
• Hàm được gọi đúng một lần cho mỗi bộ kiểm thử.

Ràng buộc

• \(1\le n\le600\,000\).
• \(1\le q\le600\,000\).
• \(1\le v[i]\le400\,000\) với mọi \(0\le i<n\).
• \(0\le l_i\le r_i<n\) với mọi \(0\le i<q\).

Phân nhóm

• Phân nhóm 1 (4 điểm): \(1\le n\le10\), \(1\le q\le100\).
• Phân nhóm 2 (6 điểm): \(1\le n,q\le100\).
• Phân nhóm 3 (17 điểm): \(1\le n,q\le1\,000\).
• Phân nhóm 4 (10 điểm): \(1\le n,q\le100\,000\) và \(1\le v[i]\le2\) với mọi \(0\le i<n\).
• Phân nhóm 5 (30 điểm): \(1\le n,q\le75\,000\).
• Phân nhóm 6 (33 điểm): Không có ràng buộc bổ sung.

Ví dụ

solve(
    10,
    {1, 1, 2, 2, 3, 3, 1, 2, 3, 4},
    2,
    {{0, 5}, {0, 8}}
)

{1, 2}

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): n q.
• Dòng \(2\): v[0] v[1] ... v[n-1].
• Dòng \(3+i\) với \(0\le i<q\): l_i r_i, sử dụng chỉ số bắt đầu từ \(0\) như giao diện solve.

Trình chấm mẫu in \(q\) dòng là các phần tử của mảng do solve trả về.