题解 | #ZJ8 用户喜好#(哈希表+二分查找)

解题思路

1.使用无序哈希表unordered_map<int,vector>存储(喜好值, 用户编号),使用二分查找的方法确定用户边界;

代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int main(){
    int n ;
    cin >> n;
    unordered_map<int, vector<int>> f; //(喜好值, 用户编号)
    for(int i = 0; i < n; i++){
        int val;
        cin >> val;
        f[val].push_back(i + 1); //从示例可看出编号从1开始
    }
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        int l, r, k;
        cin >> l;
        cin >> r;
        cin >> k;
        if(f.count(k) == 0){
            cout << 0 << endl;
            continue;
        }
        auto v = f[k];
        int pos1 = lower_bound(v.begin(), v.end(), l) - v.begin(); //大于等于l的第一个位置
        int pos2 = upper_bound(v.begin(), v.end(), r) - v.begin(); //大于r的第一个位置
        cout << pos2 - pos1 << endl; //[pos1:pos2-1]区间
    }
    return 0;
}