codeforce-1719C
# codeforces 1719C
# The problem
C. Fighting Tournament
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Burenka is about to watch the most interesting sporting event of the year — a fighting tournament organized by her friend Tonya.
n athletes participate in the tournament, numbered from 1 to n. Burenka determined the strength of the i-th athlete as an integer ai, where 1≤ai≤n. All the strength values are different, that is, the array a is a permutation of length n. We know that in a fight, if ai>aj, then the i-th participant always wins the j-th.
The tournament goes like this: initially, all n athletes line up in ascending order of their ids, and then there are infinitely many fighting rounds. In each round there is exactly one fight: the first two people in line come out and fight. The winner goes back to the front of the line, and the loser goes to the back.
Burenka decided to ask Tonya q questions. In each question, Burenka asks how many victories the i-th participant gets in the first k rounds of the competition for some given numbers i and k. Tonya is not very good at analytics, so he asks you to help him answer all the questions.Input
The first line contains one integer t (1≤t≤104) — the number of test cases. Description of the test cases follows.
The first line of each test case contains two integers n and q (2≤n≤105, 1≤q≤105) — the number of tournament participants and the number of questions.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤n) — the array a, which is a permutation.
The next q lines of a test case contain questions. Each line contains two integers i and k (1≤i≤n, 1≤k≤109) — the number of the participant and the number of rounds.
It is guaranteed that the sum of n and the sum of q over all test cases do not exceed 105.
Output
For each Burenka’s question, print a single line containing one integer — the answer to the question.
# Preface
# It’s not a very hard problem, but contains many details. This is the record when I tried:
# The basic solution for this problem is to find out if there are numbers bigger then a[i], if so, the guy with the number i CAN NOT WIN ANYBODY, else, tried to find the number of the guys AFTER HIM with smaller a[]. This number is the BIGGEST number of his victories. You might notices, if the guy is the best in the whole queue, then he can win any guys he met(depend how big the k is), others can not because they may met this guy and his game can be called “over”.
# DETAILS
-
# The first and second guy is special. They fight each other. You can see that (i>=2) can use the same formula. So you shall judge (i==1) specially. The biggest a[] shall also be judge specially. With those, you answer shall be right.
-
# However, you might get a “TLE”(Well,I did). This is how I wrote previously:
// for (i=1;i<=n;i++){
// if (a[i]==maxn) continue;
// for (j=i+1;j<=n;j++){
// if (a[j]>=a[i]) break;
// b[i]++;
//}
// b[i]++;
// if (i==1) b[i]--;
// for (j=1;j<i;j++){
// if (a[j]>a[i]){
// b[i]=0;
// break;
// }
// }
// }
# Clearly, O(n^2) is too slow. So I tried to find another way.
# We can find that the whole work can be done in LINEAR TIME. Like this:
int lld=1;
for (i=1;i<n;i++){
if (a[i]>a[i+1]){
b[lld]++;
a[i+1]=a[i];
}
else{
lld=i+1;
b[lld]++;
}
}