D-query

View as PDF
Submit solution
Points: 0.33 (partial)
Time limit: 2.25s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
© VNOI
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 0
    vominhmanh10  commented on Dec. 17, 2025, 2:15 p.m. ← edited

    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";
}

  • 9
    m1nkpk4nn  commented on Oct. 25, 2025, 2:04 p.m.

    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  commented on July 30, 2025, 5:35 p.m.

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


  • 1
    Mimi  commented on June 7, 2024, 9:31 a.m.

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


    • 11
      Cadoc  commented on June 8, 2024, 1:26 p.m.

      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  commented on Jan. 20, 2024, 12:14 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -20
      tuattsx3  commented on July 27, 2024, 1:15 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


      • -4
        kietjumper  commented on Sept. 4, 2024, 10:14 a.m.

        ???


    • -11
      nhimthuhai  commented on Jan. 20, 2024, 4:07 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -119
    LA_NTTANH  commented on Sept. 26, 2023, 12:49 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -39
    tminh_hk20  commented on April 18, 2023, 3:12 p.m. ← edit 2

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -65
      z  commented on April 18, 2023, 4:12 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -25
      thoiyen1906  commented on April 18, 2023, 3:23 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -43
      Ngumaconsi  commented on April 18, 2023, 3:20 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -30
      nthach1010  commented on April 18, 2023, 3:18 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -39
      ruby0107  commented on April 18, 2023, 3:18 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -43
      bruhlmao21  commented on April 18, 2023, 3:16 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.