题解 | #用户喜好#

import java.util.*;

class Query {
    int l, r, k, index;

    public Query(int l, int r, int k, int index) {
        this.l = l;
        this.r = r;
        this.k = k;
        this.index = index; //因为需要按查询输入的顺序打印输出，而后面会对查询排序，所以用这个字段记录输入的顺序用于输出
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) arr[i] = sc.nextInt();
        int q = sc.nextInt();
        Query[] queries = new Query[q];
        for (int i = 0; i < q; i++) queries[i] = new Query(sc.nextInt(), sc.nextInt(), sc.nextInt(), i);
        //先按喜好排，喜好相同再按左区间排，值得注意的是题目说不会出现一个查询的用户区间完全覆盖另一个查询的用户区间，这句话表明只要按左区间排好序，右区间也就排好序了
        Arrays.sort(queries, (o1, o2) -> {
            if (o1.k != o2.k) return o1.k - o2.k;
            return o1.l - o2.l;
        });
        int[] res = new int[q]; //记录结果，最后打印
        for (int i = 1; i <= n; i++) {
            int start = binarySearchExt(queries, i, arr[i]);
            for (int j = start; j < q; j++) { //从第一个满足的区间开始搜索
                if (queries[j].l > i || queries[j].r < i || queries[j].k != arr[i]) break; //遇到第一个不满足的区间就可以结束本次搜索了
                res[queries[j].index]++; //此用户满足，对应位置加1
            }
        }
        for (int i : res) System.out.println(i);
    }

    //在有序数组中找“第一个大于等于给定条件”的索引，找相同喜好下第一个右端点满足大于等于用户索引的区间
        static int binarySearchExt(Query[] queries, int index, int k) {
        int left = 0, right = queries.length - 1, mid;
        while (left < right) {
            mid = (left + right) / 2;
            if (queries[mid].k > k) {
                right = mid - 1;
            } else if (queries[mid].k == k) {
                if (queries[mid].r >= index) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}