Lời nguyền của Shizuka

Tác giả:

Dạng bài

Điểm: 300 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Shizuka đã bị dính lời nguyền sẽ kết hôn với Degisuki. Để giải được lời nguyền đó Nobita phải giải quyết bài toán sau. Cho một dãy gồm \(n\) số nguyên không âm \(a_1, a_2, a_3, ..., a_n\). Có \(q\) truy vấn \(x, l, r\), cần tính trong đoạn \(l, r\) số \(x\) xuất hiện bao nhiêu lần. Các bạn hãy giúp Nobita phá bỏ lời nguyền đó nha!!!!

Input

Dòng đầu tiên chứa 2 số \(n, q (1 \leq n, q \leq 10^5)\)
Dòng thứ hai gồm \(a_1, a_2, a_3, ..., a_n (1 \leq a_i \leq 10^6)\)
Gồm \(q\) dòng chứa \(x, l, r (1 \leq x \leq 10^6, 1 \leq l \leq r \leq n)\)

Output

Ghi ra \(q\) dòng là kết quả mỗi truy vấn

Scoring

Subtask \(1\) (\(50\%\) số điểm): \(n \cdot q \leq 10^8\)
Subtask \(2\) (\(50\%\) số điểm): không ràng buộc gì thêm

Example

Test 1

Input

Output

Bình luận

-2

hint

Ý tưởng để giải bài toán này là sử dụng cấu trúc dữ liệu hiệu quả để nhanh chóng trả lời các truy vấn về số lần xuất hiện của một số trong một khoảng cho trước.

code

chép tao báo admin à

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);
    unordered_map<int, vector<int>> freq;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        freq[a[i]].push_back(i);
    }

    while (q--) {
        int x, l, r;
        cin >> x >> l >> r;

        if (freq.find(x) == freq.end()) {
            cout << 0 << '\n';
            continue;
        }

        auto& indices = freq[x];
        auto it1 = lower_bound(indices.begin(), indices.end(), l);
        auto it2 = upper_bound(indices.begin(), indices.end(), r);

        cout << distance(it1, it2) << '\n';
    }

    return 0;
}

15 bình luận nữa