Lời nguyền của Shizuka

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
a520huynm
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 
5 5
2 1 5 1 3
4 1 5
1 1 2
2 1 5
1 1 5
5 3 3
Output 
0
1
1
2
1

Bình luận


  • 0
    trananhminh_lvt_k39    8:11 p.m. 10 Tháng 11, 2024

    Đề cho câu chuyện hấp dẫn đấy


    • 0
      NguyenDangNhan153    8:55 p.m. 2 Tháng 9, 2024

      mik fan degisuki :))


      • 0
        ttsang    9:09 p.m. 31 Tháng 8, 2024

        tui sẽ cứu degisuki nên code đây:
        #include <bits/stdc++.h>
        using namespace std;
        int main()
        {
        int n, q;
        cin >> n >> q;
        vector<int> a(n + 1);
        unordered_map<int, vector\<int>> positions;
        for (int i = 1; i <= n; i++) {
        cin >> a[i];
        positions[a[i]].push_back(i);
        }
        while (q--) {
        int x, l, r;
        cin >> x >> l >> r;
        if (positions.find(x) == positions.end()) {
        cout << 0 << endl;
        continue;
        }
        const vector<int>& pos = positions[x];
        auto it_l = lower_bound(pos.begin(), pos.end(), l);
        auto it_r = upper_bound(pos.begin(), pos.end(), r);
        int result = it_r - it_l;
        cout << result << endl;
        }
        return 0;
        }


        • 0
          doraemon    3:30 p.m. 28 Tháng 8, 2024

          tui đã giải cứu đc shizuka


          • -2
            doanngocgiahung2013    11:25 a.m. 4 Tháng 8, 2024
            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;
}

            • -5
              doanngocgiahung2013    11:18 a.m. 4 Tháng 8, 2024

              Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


              • 0
                xthabao1    8:33 p.m. 8 Tháng 7, 2024

                cần 1 cái hint 🙏🙏🙏🙏🙏🙏🙏

                1 phản hồi

                • -3
                  PhucDepZai    3:33 p.m. 8 Tháng 7, 2024

                  degisuki là ai vay

                  2 phản hồi

                  • 0
                    xthabao1    11:58 p.m. 7 Tháng 7, 2024

                    Khó khăn cho Nobita đây

                    1 phản hồi

                    • -4
                      anhduc11092014    11:19 a.m. 5 Tháng 6, 2024

                      tên hay vãiiiiiiiiiiiiiiiiiiiiiiii

                        • 6 bình luận nữa