Envío 4990

Código

import java.util.HashMap;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Arrays;
import java.util.stream.Collectors;

class Main{ /* arr is sorted without duplicates */ 
    public static int index(List<Integer> arr, int target){
        int l = 0;
        int r = arr.size() - 1;

        while(l <= r){
            int m = (l + r) >> 1;                
            if(arr.get(m) == target)    
                return m;
            else if(arr.get(m) < target)
                l = m + 1;            
            else
                r = m - 1;
        }
        return -1;
    }

    public static int query(List<Integer> arr, int target){
        if(arr == null || target < 0)   
            return 0;
        int l = 0;              
        int r = arr.size() - 1;
        int res = -1;

        while(l <= r){
            int m = (l + r) >> 1; // safe because of bounds     
            if(arr.get(m) <= target){
                res = m;                    
                l = m + 1;
            } else {
                r = m - 1;      
            }   
        }
        return res + 1;
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);   
        int N = scanner.nextInt();
        int[] nums  = new int[N];

        for(int i = 0; i < N; i++)
            nums[i] = scanner.nextInt();                    
    
        
        int[] nnums = Arrays.copyOf(nums, nums.length);
        Arrays.sort(nnums);
        

        List<Integer> snums = new ArrayList<Integer>(); 
        int prev = Integer.MIN_VALUE;
        for(int i = 0; i < N; i++){
            if(prev != nnums[i])            
                snums.add(nnums[i]);
            prev = nnums[i];
        }


        ArrayList<ArrayList<Integer>> l = new ArrayList<ArrayList<Integer>>(snums.size());
        for(int i = 0; i < snums.size(); i++)  
            l.add(new ArrayList<Integer>());

        for(int i = 0; i < N; i++){
            int idx = index(snums, nums[i]);                 
            l.get(idx).add(i);
        }

        int Q = scanner.nextInt();      
        int L, R, X, left, right, idx;
        L = R = X = left = right = 0;
        List<Integer> m;    
        for(int i = 0; i < Q; i++){
            L = scanner.nextInt();
            R = scanner.nextInt();
            X = scanner.nextInt();
            idx = index(snums, X);
            if(idx == -1){
                System.out.println(0);
                continue;
            }
            m = l.get(idx);
            left = query(m, L - 1);
            right = query(m, R);
            System.out.println(right - left);
        }
    }
}