今日头条C++后台研发编程题

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <unordered_map>

#define FIN freopen("input.txt", "r", stdin)

using namespace std;
const int MAXN = 3e5 + 5;
const int MAXM = 50 + 5;
int n, q, l, r, k;
unordered_map<int,int> um;
int np[MAXN];
struct Q{
    int l, r, k, id;
    bool operator<(const Q&a) const{
        if(l == a.l) return r < a.r;
        return l < a.l;
    }
}XW[MAXN];
vector<pair<int,int> > vec;

int main() {
    //FIN;
    while(~scanf("%d", &n)){
        for(int i = 1;i <= n;++ i){
            scanf("%d", &np[i]);
        }
        scanf("%d", &q);
        for(int i = 0;i < q;i ++){
            scanf("%d%d%d", &XW[i].l, &XW[i].r, &XW[i].k);
            XW[i].id = i;
        }
        sort(XW, XW + q);
        um.clear();
        vec.clear();
        int l = 1, r = 0;
        for(int i = 0;i < q;++ i){
            if(r < XW[i].r){
                for(r = r + 1;r < XW[i].r; ++ r){
                    um[np[r]] ++;
                }
                um[np[r]] ++;
            }
            if(XW[i].l < l){
                for(l = l - 1;XW[i].l < l;-- l){
                    um[np[l]] ++;
                }
                um[np[l]] ++;
            }
            if(XW[i].r < r){
                for(;XW[i].r < r;-- r){
                    um[np[r]] --;
                }
            }
            if(l < XW[i].l){
                for(;l < XW[i].l;++ l){
                    um[np[l]] --;
                }
            }
            vec.push_back(make_pair(XW[i].id, um[XW[i].k]));
        }
        sort(vec.begin(), vec.end());
        for(int i = 0;i < vec.size();++ i){
            printf("%d\n", vec[i].second);
        }
    }
    return 0;
}