用户喜好

题目难度：中等

知识点：二分查找，STL，vector，map

解题思路：
1.输入人数，根据人数建立喜好度vector user(n)。
2.输入查询组数，根据组数建立左右区间数字l和r，以及查询喜好度数字k的vector。
3.建立喜好度与用户标号之间的对应关系map<int,vector< int > >，这里的第一个参数是喜好度数值，第二个参数vector<int>是该喜好度对应的用户标号。如题例中喜好度为1时，该vector中保存[1]；喜好度为3时，该vector中保存[3,4]。
4.开始查询。根据k[i]中的喜好度查询数值，可以找到map中该喜好度对应的vector p。使用二分查找，可以在p中找到第一个大于等于l[i]的位置，以及第一个大于r[i]的位置。将两个位置相减即为所求人数，保存到res中。如题例所示，输入查询组数为：</int>

1 2 1
2 4 5
3 5 3

• 当查询1 2 1这一组时，k[i]=1，l[i]=1，r[i]=2。根据k[i]从map中获得喜好度为1的vector p，它是[1]。那么lower_bound(p.begin(),p.end(),1)会返回一个指向1的迭代器，upper_bound(p.begin(),p.end(),2)会返回一个p.end()的迭代器，这时两个迭代器相减得1，输出1。
• 当查询2 4 5这一组时，k[i]=5，l[i]=2，r[i]=4。根据k[i]从map中获得喜好度为5的vector p，它是[5]。那么lower_bound(p.begin(),p.end(),2)会返回一个指向5的迭代器，upper_bound(p.begin(),p.end(),4)也会返回一个指向5的迭代器，这时两个迭代器相减得0，输出0。
• 当查询3 5 3这一组时，k[i]=3，l[i]=3，r[i]=5。根据k[i]从map中获得喜好度为3的vector p，它是[3，4]。那么lower_bound(p.begin(),p.end(),3)会返回一个指向3的迭代器，upper_bound(p.begin(),p.end(),5)会返回一个p.end()的迭代器，这时两个迭代器相减得2，输出2。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
class solution
{
public:
    void func()
    {
        int n,q;
        cin>>n;                           //输入人数
        vector<int> user(n);
        for(int i=0;i<n;i++)
            cin>>user[i];                 //录入喜好度
        cin>>q;                           //查询组数
        vector<int> l(q),r(q),k(q);
        for(int i=0;i<q;i++)
            cin>>l[i]>>r[i]>>k[i];        //查询区间起点l，终点r，喜好度k
        map<int,vector<int> > mp;
        for(int i=0;i<n;i++)
            mp[user[i]].push_back(i+1);   //每个喜好度对应用户的标号存入vector与喜好度对应（注意下标+1）
        vector<int> res(q,0);             //结果
        for(int i=0;i<q;i++)              //根据组数循环得到结果
        {
            if(mp.count(k[i])!=0)         //如果该喜好度用户数不为0
            {
                vector<int> p = mp[k[i]]; //提出该喜好度对应用户标号的vector
                //二分查找
                //lower_bound(起始地址，结束地址，要查找的数值x) 
                //返回的是第一次出现大于等于x的地址
                //upper_bound(起始地址，结束地址，要查找的数值x) 
                //返回的是第一个大于x的地址
                //从p中找到≤r[i]的位置减去≥l[i]的位置，即为结果所求人数。
                res[i] = upper_bound(p.begin(), p.end(), r[i]) - lower_bound(p.begin(), p.end(), l[i]);
            }
        }
        for(int i = 0; i < q; ++i)
            cout << res[i] << endl;
    }
};