这个题其实想要实现并不复杂 我只花了几分钟就搞清楚了步骤

用一个数组标记对应的用户喜好值 最后遍历 若与指定喜好值相等 res++

#include<iostream>
using namespace std;
int a[300001];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int q;
    cin>>q;
    while(q--){
        int res=0;
        int l,r,k;
        cin>>l>>r>>k;
        for(int j=l;j<=r;j++){
            if(a[j]==k)res++;
        }
        cout<<res<<endl;
    }
    return 0;
}

这么简单? 我感到字节这样的大厂也没那么遥远……

但这样做是超时的 因为在查找时从头到尾遍历耗费了大量时间 所以我们必须进行优化

优化思路一—前缀和

创建一个二维的前缀和数组 prefix[k][i]，表示在前 i 个元素中，值为 k 的元素出现的次数。这样，对于每个查询 [l, r, k]，可以通过计算 prefix[k][r] - prefix[k][l-1] 来快速得到答案

这种方法的时间复杂度为 O(n) 来构建前缀和，查询的时间复杂度为 O(1)

代码如下:

#include<iostream>
#include<unordered_map>
using namespace std;
int a[300001];
unordered_map<int, int> prefix[300001];  
int main() {
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            prefix[i][a[j]]++;
        }
    }
    int q;
    cin >> q;
    
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;  
        int res = prefix[r][k] - prefix[l-1][k];
        cout << res << endl;
    }
    return 0;
}

优化思路二—哈希表+二分查找

这个思路和刚刚的前缀和差不多 预处理时间复杂度为O(n) 查询的复杂度为O(log k)

说实话我对这个C++自带的unordered_map很不熟悉 而这几天做到的算法题都或多或少用到了这个东西 所以我应用起来很难受 后面我会专门介绍一下unordered_map的使用

代码贴在下面

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

int main(){
	int n; cin >> n;
	vector<int> like(n+1, 0);
	for (int i = 1; i <= n; ++i)    cin >> like[i];
	unordered_map<int, vector<int>> m;
	for (int i = 1; i <= n; ++i)          m[like[i]].push_back(i);
	int q; 
	cin >> q;
	for (int i = 0; i < q; ++i){
		int l, r, num;
		cin >> l >> r >> num;
		if (m.count(num) == 0){
			cout << 0 << endl;
			continue;
		}
		auto l_it = lower_bound(m[num].begin(), m[num].end(), l);
		auto r_it = upper_bound(m[num].begin(), m[num].end(), r);
		cout << r_it - l_it << endl;
	}
	return 0;
}