Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Đếm giá trị phân biệt trên đoạn

    Cho dãy số a1,…,ana_1, \dots, a_na1​,…,an​ và qqq truy vấn. Mỗi truy vấn (l,r)(l, r)(l,r) hỏi số giá trị phân biệt trong đoạn con al,…,ara_l, \dots, a_ral​,…,ar​.

    Vì các truy vấn được biết trước (offline), hãy dùng thuật toán Mo để xử lý tất cả trong O((n+q)n)O((n+q)\sqrt{n})O((n+q)n​).

    Ví dụ: Dãy [1,2,1,3][1,2,1,3][1,2,1,3], truy vấn (1,4)(1,4)(1,4) có các giá trị phân biệt {1,2,3}\{1,2,3\}{1,2,3} nên đáp án là 333.

    • Định dạng đầu vào:

      Dòng đầu chứa nnn và qqq. Dòng thứ hai chứa nnn số nguyên. qqq dòng tiếp theo, mỗi dòng hai số l rl\ rl r.

    • Ràng buộc đầu vào:

      1≤n,q≤1051 \le n, q \le 10^51≤n,q≤105, ∣ai∣≤109|a_i| \le 10^9∣ai​∣≤109, 1≤l≤r≤n1 \le l \le r \le n1≤l≤r≤n.

    • Định dạng đầu ra:

      Với mỗi truy vấn (theo thứ tự đầu vào), in số giá trị phân biệt trên một dòng.

    Ví dụ:

    Đầu vào:

    4 1
1 2 1 3
1 4

    Đầu ra:

    3

    Giải thích:

    Đoạn con là toàn dãy [1,2,1,3]. Các giá trị xuất hiện là 1, 2, 3 (giá trị 1 lặp lại không tính thêm), nên số giá trị phân biệt là 3.

    Đang tải editor...