User preferences

In order to continuously optimize the recommendation effect , Today's headlines store and process huge amounts of data every day . Let's say there's a scenario ： We label users first and then according to their registration time , For a class of articles , Each user has different preference values , We will want to know the users registered in a certain period of time （ A group of users connected by labels ） in , How many users like this kind of articles? The value is k. For some special reason , The user interval of one query will not completely cover the user interval of another query ( non-existent L1<=L2<=R2<=R1).

 

Input description :

 Input ：  The first 1 Behavior n Represents the number of users   The first 2 Behavior n It's an integer , The first i The number representing the user is i Users' preference for certain types of articles   The first 3 Act as a positive integer q Represents the number of groups queried    The first 4 Go to the first place （3+q） That's ok , Each row contains 3 It's an integer l,r,k Represents a set of queries , That is, the label is l<=i<=r The user's preference for this kind of article is k Number of users .  Data range n <= 300000,q<=300000 k Integer. 

Output description :

 Output ： altogether q That's ok , An integer in each line indicates that the preference value is k Number of users 

Example 1

Input

5
1 2 3 3 5
3
1 2 1
2 4 5
3 5 3

Output

1
0
2

explain

 Sample explanation :
 Yes 5 Users , The preference values are 1、2、3、3、5,
 The first group asked about the label [1,2] The user preference value of is 1 The number of users is 1
 The second group asked about the label [2,4] The user preference value of is 5 The number of users is 0
 The third group asked about the label [3,5] The user preference value of is 3 The number of users is 2

 

Ideas

Build a map, Different preference values are used as key, Subscript as val, This key Corresponding val Form a array. Then look for k Corresponding array In line with l～r The interval of , This step is done by dichotomy

#include <bits/stdc++.h>
using namespace std;
int main()
{
    unordered_map<int, vector<int>> key_m;
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int tem;cin>>tem;
        key_m[tem].push_back(i);
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int l,r,k;cin>>l>>r>>k;
        unordered_map<int, vector<int>>::iterator itera=key_m.find(k);
        if(itera==key_m.end()) cout<<0<<endl;
        else{
            auto ie1=lower_bound(itera->second.begin(),itera->second.end(),l);
            auto ie2=upper_bound(itera->second.begin(), itera->second.end(),r);
            cout<<ie2-ie1<<endl;
        }
    }
    return 0;
}