D-query

Xem dạng PDF
Gửi bài giải
Điểm: 0,33 (OI)
Giới hạn thời gian: 2.25s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
© VNOI
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một dãy số ~n~ phần tử ~a_{1}~, ~a_{2}~, ..., ~a_{n}~ và một số các truy vấn ~d~. Một truy vấn ~d~ là một cặp (~i~, ~j~) (~1~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~n~). Với mỗi truy vấn ~d~(i, ~j~), bạn cần trả về số phần tử phân biệt nằm trong dãy con ~a_{i}~, ~a_{i+1}~, ..., ~a_{j}~.

Input

  • Dòng ~1~: ~n~ (~1~ ~\leq~ ~n~ ~\leq~ ~30000~).
  • Dòng ~2~: ~n~ số ~a_{1}~, ~a_{2}~, ..., ~a_{n}~ (~1~ ~\leq~ ~a_{i}~ ~\leq~ ~10^{6}~).
  • Dòng ~3~: ~q~ (~1~ ~\leq~ ~q~ ~\leq~ ~200000~), số lượng truy vấn- ~d~.
  • Trong ~q~ dòng sau, mỗi dòng chứa ~2~ số ~i~, ~j~ biểu thị một truy vấn-d (~1~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~n~).

Output

  • Với mỗi truy vấn ~d~(~i~, ~j~), in ra số phần tử phân biệt thuộc dãy con ~a_{i}~, ~a_{i+1}~, ..., ~a_{j}~ trên một dòng.

Sample Input

5
1 1 2 1 3
3
1 5
2 4
3 5

Sample Output

3
2
3

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    vominhmanh10  đã bình luận lúc 17, Tháng 12, 2025, 14:15 ← chỉnh sửa

    hướng giải với BIT cho xử lý offline

    #include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define fast_func inline __attribute__((always_inline))
#define all(v) v.begin(), v.end()
#define IO ios::sync_with_stdio(0); cin.tie(nullptr)
const ll maxn = 1e6 + 5, inf = 1e18;
int BIT[maxn], n, q, l, r, onl[maxn], L[maxn];
void add(int i, int x) {
    if (i == 0) return;
    for (; i <= n; i += i & -i) BIT[i] += x;}
int sum(int i) {
    int res = 0;
    for (; i > 0; i -= i & -i) res += BIT[i];
    return res;
}
int range_query(int l, int r) {return sum(r) - sum(l - 1);}
int main() {
    IO;
    cin >> n; vector<int> a(n + 1);
    vector< array< int, 3>> queries;
    unordered_map< int, int> last;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (last.find(a[i]) == last.end()) L[i] = 0;
        else L[i] = last[a[i]];
        last[a[i]] = i;
    }
    int q; cin >> q;
    for (int id = 0; id < q; ++id) {
        cin >> l >> r;
        queries.pb({r, l, id});
    }
    sort(all(queries));
    int R = 0;
    for (auto [r, l, id]: queries) {
        while (r > R) {
            add(R + 1, 1);
            add(L[R + 1], -1);
            R++;
        }
        onl[id] = range_query(l, r);
    }
    for (int i = 0; i < q; ++i) cout << onl[i] << "\n";
}

  • 8
    m1nkpk4nn  đã bình luận lúc 25, Tháng 10, 2025, 14:04

    Một cách giải khác không dùng MO / BIT

    Data Structures:

    Persistent Segment Tree

    Ý Tưởng:

    Ta sẽ tạo N version của PST (từ giờ sẽ là viết tắt của Persistent Segment Tree), mỗi version quản lý thông tin về các phần tử xuất hiện đến vị trí đó.

    Với mỗi vị trí i trong mảng, ta giữ lại vị trí xuất hiện trước đó của phần tử a[i].

    Khi thêm phần tử mới tại i, nếu phần tử đó đã xuất hiện ở vị trí pos[a[i]] trước đó, ta cập nhật PST:

    Tắt (gán 0) vị trí cũ pos[a[i]] vì phần tử này không còn tính tại vị trí đó nữa.

    Bật (gán 1) vị trí hiện tại i vì phần tử mới xuất hiện ở đây.

    Như vậy, mỗi version i của PST sẽ biểu diễn trạng thái phần tử nào đang xuất hiện lần cuối tại vị trí nào, và tại mỗi version ta biết tổng các điểm bật, tức đồng nghĩa với việc đếm số phần tử phân biệt trong prefix [1 ... i].

    Để trả lời truy vấn đếm số phần tử phân biệt trong đoạn [l, r], ta truy vấn version r trên cây phân đoạn và lấy tổng trong đoạn [l, r].

    Code:

    ideone

    Nếu thấy Sol hay hãy để lại cho mình 1 Upvote nhé, chúc các bạn AC <33


  • 0
    tranminhphuong3579  đã bình luận lúc 30, Tháng 7, 2025, 17:35

    Sol thuật toán Mo cho bạn nào cần nhé https://ideone.com/ou8MXl


  • 1
    Mimi  đã bình luận lúc 7, Tháng 6, 2024, 9:31

    ai có sol cách làm chia căn k ạ? thathanks


    • 11
      Cadoc  đã bình luận lúc 8, Tháng 6, 2024, 13:26

      bạn dùng Mo quản lý cnt[i] là số lần xuất hiện của i tại truy vấn đang xét tới á, xong cứ add và xóa như Mo bth thôi


  • -12
    chunguyen2k8  đã bình luận lúc 20, Tháng 1, 2024, 12:14

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -20
      tuattsx3  đã bình luận lúc 27, Tháng 7, 2024, 13:15

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • -4
        kietjumper  đã bình luận lúc 4, Tháng 9, 2024, 10:14

        ???


    • -11
      nhimthuhai  đã bình luận lúc 20, Tháng 1, 2024, 16:07

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -118
    LA_NTTANH  đã bình luận lúc 26, Tháng 9, 2023, 0:49

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -39
    tminh_hk20  đã bình luận lúc 18, Tháng 4, 2023, 15:12 ← sửa 2

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -65
      z  đã bình luận lúc 18, Tháng 4, 2023, 16:12

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -25
      thoiyen1906  đã bình luận lúc 18, Tháng 4, 2023, 15:23

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -43
      Ngumaconsi  đã bình luận lúc 18, Tháng 4, 2023, 15:20

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -30
      nthach1010  đã bình luận lúc 18, Tháng 4, 2023, 15:18

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -39
      ruby0107  đã bình luận lúc 18, Tháng 4, 2023, 15:18

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -43
      bruhlmao21  đã bình luận lúc 18, Tháng 4, 2023, 15:16

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.