OpenJudge

C17H:Reverse K-th Problem

总时间限制:
8000ms
内存限制:
262144kB
描述

FancyCoder once encountered a challenging problem called "K-th Problem". Here is the description: given an array of N integers A[1],A[2],...,A[N] and some queries, each query asks for the K-th largest element among A[L],A[L+1],...,A[R].

After learning a lot of data structures, FancyCoder finds this problem can be solved effectively by "Partition Tree" or "Persistent Segment Tree" (alias: "Chairman Tree").


However, FancyCoder is still not satisfied. He raises another problem called "Reverse K-th Problem". The description is also simple: given an array of N integers A[1],A[2],...,A[n] and some queries, each query asks for the number of continuous subsequences of the array in which the K-th largest element is X.


输入
The first line contains an integer T (1 <= T <= 5), indicating the number of test cases.

For each test case:

The first line contains two integers N and Q (1 <= N <= 2,000, 1 <= Q <= 2,000,000), indicating there are N integers in the array and Q queries.

The second line contains N integers between 1 and N, indicating the element of the array.

Then Q lines follow, the i-th line contains two integers Ki and Xi (1 <= Ki,Xi <= N), indicating that the i-th query asks for the number of continuous subsequences of the array in which the Ki-th largest element is Xi.
输出
For each test case:

Output Q lines, the i-th line contains one integer, indicating the answer to the i-th query.
样例输入
2
3 2
1 1 2
1 1
2 1
5 4
1 4 3 2 5
2 3
1 4
4 1
2 5
样例输出
3
3
5
6
1
0
全局题号
15053
添加于
2017-05-21
提交次数
182
尝试人数
25
通过人数
19