Stable market

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Sometimes, the stability of a stock market is at least as important as rapid price changes.
Let a stable block be a maximal consecutive block of days with same stock prices.
Moreover, let a stable block of order K be a stable block of length at least K.
For example, if stock prices for 7 consecutive days are: 20, 10, 10, 7, 7, 7, 10, then there are 4 stable blocks there: [20], [10, 10], [7, 7, 7] and [10]. Moreover, there are: 0 stable blocks of order 4 or higher
 1 stable block of order 3: [7, 7, 7]
 2 stable block of order 2: [10, 10], [7, 7, 7]
 4 stable block of order 1: [20], [10, 10], [7, 7, 7] and [10]
Given historical prices of a stock across N days, the goal is to answer Q customers' questions.
The ith question contains three integers L_{i}, R_{i} and K_{i}. It asks for the number of stable blocks of order K_{i}, if only the stock prices of the days in the range L_{i}, R_{i} are considered.
Input
 In the first line there is a single integer T, denoting the number of test cases to handle. After that the description of T test cases follow.
 The first line of each test case contains two spaceseparated integers N and Q, denoting respectively, the number of days for which the stock prices are given, and the number of questions to answer.
 The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N}, where A_{i} denotes the price of the stock on the ith day.
 Q lines follow. In the ith of them there are three spaceseparated integers L_{i}, R_{i} and K_{i} denoting the ith query.
Output
For each test case, print answers to all queries in the test case, one per line.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ A_{i} ≤ 10^{6}
 1 ≤ L_{i} ≤ R_{i} ≤ N
 1 ≤ K_{i} ≤ R_{i}  L_{i} + 1
Subtasks
Subtask #1: (10 points)
 1 ≤ N, Q ≤ 3000
Subtask #2: (90 points)
 original constraints
Example
Input: 2 8 5 20 10 10 10 7 7 7 10 2 6 2 3 6 2 3 6 3 3 8 3 3 8 1 3 2 27 27 27 1 3 1 2 2 1 Output: 2 2 0 1 3 1 1
Explanation
There are two test cases to handle
Test case #1:
There are 8 days for which prices are given and 5 queries to handle.
The first query asks for the number of stable blocks of order 2 in range [2, 6], which corresponds to prices 10 10 10 7 7. The answer is 2 because there are two such blocks: 10 10 10 and 7 7.
The second query asks for the number of stable blocks of order 2 in range [3, 6], which corresponds to prices 10 10 7 7. The answer is 2 because there are two such blocks: 10 10 and 7 7.
The third query asks for the number of stable blocks of order 3 in range [3, 6], which corresponds to prices 10 10 7 7. The answer is 0 because there is no stable block of order 3 there (maximum order of a stable block is 2).
The fourth query asks for the number of stable blocks of order 3 in range [3, 8], which corresponds to prices 10 10 7 7 7 10. The answer is 1 because the only stable block of order 3 here is 7 7 7.
The fifth query asks for the number of stable blocks of order 1 in range [3, 8], which corresponds to prices 10 10 7 7 7 10. The answer is 3 because there are 3 stable blocks of order 1 there: 10 10, 7 7 7 and 10.
Test case #2:
There are 3 days for which prices are given and 2 queries to handle.
The first query asks for the number of stable blocks of order 1 in range [1, 3], which corresponds to prices 27 27 27. The answer is 1 because the only such block there is 27 27 27.
The second query asks for the number of stable blocks of order 1 in range [2, 2], which corresponds to a single price 27. The answer is 1 because the only such block there is 27.
Author:  pkacprzak 
Editorial  https://discuss.codechef.com/problems/SMARKET 
Tags  april17, medium, pkacprzak, segmenttree 
Date Added:  29032017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 