Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
Given an array of N elements, indexed from 0 to N-1. Now you are given some queries in the form [L, R] inclusive. Your task is to find the number of occurrence of the highest value from L to R.
Let's say, an array A = {1001, 3, 5, 5, 99}, and L = 2, R = 3. So, here the highest value from index 2 to 3 is 5 and the number of occurrence of 5 is exactly 2. So, you have to print 2.
Input begins with an integer T (1 ≤ T ≤ 20), denoting the number of test cases.
Each case starts with two integers N and Q (1 ≤ N, Q ≤ 104). The next line contains N space separated integers forming the array A (-2x105 < A[i] < 2x105).
The next Q lines will contain the queries which is in the form L to R (0 ≤ L ≤ R < N).
For each test case, print the case number in a single line. Then for each query you have to print the number of occurrence of the maximum number between index L to R.
Input | Output |
---|---|
1 5 3 1001 3 5 5 99 1 2 2 3 0 4 | Case 1: 1 2 1 |
73% Solution Ratio
arknaveEarliest,
MR.Jukerburg11Fastest, 0.0s
Asif_AlimLightest, 487 kB
MR.Jukerburg11Shortest, 940B
Login to submit
apply segment tree