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.
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