Help needed in finding the logic of the question
You are given N points in a plane (numbered 1 through N); for each valid i, the i-th point is Pi=(i,Ai). There are N−1 line segments between them (numbered 1 through N−1); for each valid i, the i-th line segment is formed by connecting the points Pi and Pi+1.
You should answer Q queries. In each query, a laser beam is fired horizontally to the right, from a point (x1,y) to a point (x2,y) (where it stops and does not propagate further). Find the number of line segments it collides with on the way.
The beam is considered to collide with a line segment if it intersects or touches this segment, except when the left endpoint of this segment is (x2,y) or its right endpoint is (x1,y).
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and Q.
The second line contains N space-separated integers A1,A2,…,AN.
Each of the next Q lines contains three space-separated integers x1, x2 and y describing a query.
Output
For each query, print a single line containing one integer ― the number of line segments the beam collides with.
Constraints
1≤T≤5
2≤N≤100,000
1≤Q≤100,000
1≤Ai≤10^9 for each valid i
1≤x1<x2≤N
1≤y≤10^9
Example Input
1
4 3
1 3 5 1
2 4 4
1 2 3
1 4 1
Example Output
2
1
2
Explanation
Example case 1:
For the first query, the beam collides with the 2-nd line segment and the 3-rd line segment.
For the second query, the beam collides only with the 1-st line segment. We do not consider it to collide with the second line segment, since its left endpoint is (x2,y).
For the third query, the beam collides with the 1-st line segment and the 3-rd line segment.
You should answer Q queries. In each query, a laser beam is fired horizontally to the right, from a point (x1,y) to a point (x2,y) (where it stops and does not propagate further). Find the number of line segments it collides with on the way.
The beam is considered to collide with a line segment if it intersects or touches this segment, except when the left endpoint of this segment is (x2,y) or its right endpoint is (x1,y).
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and Q.
The second line contains N space-separated integers A1,A2,…,AN.
Each of the next Q lines contains three space-separated integers x1, x2 and y describing a query.
Output
For each query, print a single line containing one integer ― the number of line segments the beam collides with.
Constraints
1≤T≤5
2≤N≤100,000
1≤Q≤100,000
1≤Ai≤10^9 for each valid i
1≤x1<x2≤N
1≤y≤10^9
Example Input
1
4 3
1 3 5 1
2 4 4
1 2 3
1 4 1
Example Output
2
1
2
Explanation
Example case 1:
For the first query, the beam collides with the 2-nd line segment and the 3-rd line segment.
For the second query, the beam collides only with the 1-st line segment. We do not consider it to collide with the second line segment, since its left endpoint is (x2,y).
For the third query, the beam collides with the 1-st line segment and the 3-rd line segment.
This smells like a "competetive" question, where you show your skills. "I don't understand the question" is a valid level of skill.
Draw the lines on a paper.
Draw the lines on a paper.
Topic archived. No new replies allowed.