题解 | #渴望力量吗#

我用的哈希map和二分查找。 map的key是喜爱值，value是List。list存喜爱值相同的人的标号。 因为标号从小到大有序，list里的标号也是升序的，可以二分查找。 查找标号[l,r]中喜爱值为k的数量。二分查找list中第一个 >= l 的标号的下标posl,和最后一个 <= r 的标号的下标posr。 如果[posl,posr]属于[l,r],则posr - posl + 1 就是喜爱值为k的标号的数量。

import java.util.*;

public class Main54 {

// 找第一个 >= x的索引
static int erfenl(List<Integer> list, int x) {
    int l = 0;
    int r = list.size() - 1;
    int mid;
    int ans = -1;
    while (l <= r) {
        mid = (l + r) / 2;
        if (list.get(mid) >= x) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

// 找最后一个 <= x的索引
static int erfenr(List<Integer> list, int x) {
    int l = 0;
    int r = list.size() - 1;
    int mid;
    int ans = -1;
    while (l <= r) {
        mid = (l + r) / 2;
        if (list.get(mid) <= x) {
        	ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    //以防多组输入
    while (scan.hasNext()) {
        int n = scan.nextInt();
        Map<Long, List<Integer>> map = new HashMap<>();

        for (int i = 1; i <= n; i++) {
            long love = scan.nextLong();
            // 如果不存在该key，先放入一个空列表
           if(!map.containsKey(love)) {
        	   map.put(love, new ArrayList<>());
           }
            //存在则将下标加入队列
            map.get(love).add(i);
        }

        int q = scan.nextInt();
        for (int i = 0; i < q; i++) {
            int l = scan.nextInt();
            int r = scan.nextInt();
            long k = scan.nextLong();

            if (!map.containsKey(k)) {
                System.out.println(0);
                continue;
            }

            List<Integer> list = map.get(k);

            //找list里第一个 >= l 的位置
            int posl = erfenl(list, l);

            //找list里最后一个 <= r 的位置
            int posr = erfenr(list, r);
            //若标号[l,r]包含[posl,posr]，则输出统计的数量
            if(posl != -1 && posr != -1) {
            	System.out.println(posr - posl + 1);
            }
            else {
            	System.out.println(0);
            }
        }
    }
    scan.close();
}

}