二分--求區間内有多個num

為了不斷優化推薦效果，今日頭條每天要存儲和處理海量資料。假設有這樣一種場景：我們對使用者按照它們的注冊時間先後來标号，對于一類文章，每個使用者都有不同的喜好值，我們會想知道某一段時間内注冊的使用者（标号相連的一批使用者）中，有多少使用者對這類文章喜好值為k。因為一些特殊的原因，不會出現一個查詢的使用者區間完全覆寫另一個查詢的使用者區間(不存在L1<=L2<=R2<=R1)。

輸入描述:

輸入： 第1行為n代表使用者的個數 第2行為n個整數，第i個代表使用者标号為i的使用者對某類文章的喜好度 第3行為一個正整數q代表查詢的組數 第4行到第（3+q）行，每行包含3個整數l,r,k代表一組查詢，即标号為l<=i<=r的使用者中對這類文章喜好值為k的使用者的個數。 資料範圍n <= 300000,q<=300000 k是整型

輸出描述:

輸出：一共q行，每行一個整數代表喜好值為k的使用者的個數

輸入例子1:

5

1 2 3 3 5

3

1 2 1

2 4 5

3 5 3

輸出例子1:

1

2

例子說明1:

樣例解釋:

有5個使用者，喜好值為分别為1、2、3、3、5，

第一組詢問對于标号[1,2]的使用者喜好值為1的使用者的個數是1

第二組詢問對于标号[2,4]的使用者喜好值為5的使用者的個數是0

第三組詢問對于标号[3,5]的使用者喜好值為3的使用者的個數是2

#include <bits/stdc++.h>

using namespace std;

bool sort_cmp(const pair<int, int> &A, const pair<int, int> &B)
{
    return A.first == B.first ? A.second < B.second :
        A.first < B.first;
}

struct find_first_cmp {
    bool operator()(const pair<int, int> &P, int k) const
    {
        return P.first < k;
    }

    bool operator()(int k, const pair<int, int> &P) const
    {
        return k < P.first;
    }
};

struct find_second_cmp {
    bool operator()(const pair<int, int> &P, int k) const
    {
        return P.second < k;
    }

    bool operator()(int k, const pair<int, int> &P) const
    {
        return k < P.second;
    }
};

int main()
{
    int n, q;
    while (EOF != scanf("%d", &n)) {
        vector<pair<int, int> > arr;
        for (int i = 0, x; i < n; cin >> x, arr.emplace_back(x, ++i)) {}
        sort(arr.begin(), arr.end(), sort_cmp);

        for (scanf("%d", &q); q--;) {
            int L, R, k;
            scanf("%d%d%d", &L, &R, &k);
            pair<vector<pair<int, int> >::iterator, vector<pair<int, int> >::iterator> sd =
                equal_range(arr.begin(), arr.end(), k, find_first_cmp{});
            printf("%d\n", upper_bound(sd.first, sd.second, R, find_second_cmp{}) -
                lower_bound(sd.first, sd.second, L, find_second_cmp{}));
        }
    }
    return 0;
}