Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Vivek likes playing with lasers, but his friend Divyansh says that reading biographies is much more interesting. In order to prove that lasers are fun too, Vivek proposed an interesting task involving them:

You are given $N$ points in a plane (numbered $1$ through $N$); for each valid $i$, the $i$-th point is $P_{i} = (i, A_{i})$. 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 $P_{i}$ and $P_{i+1}$.

You should answer $Q$ queries. In each query, a laser beam is fired horizontally to the right, from a point $(x_{1}, y)$ to a point $(x_{2}, 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 $(x_{2}, y)$ or its right endpoint is $(x_{1}, 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 $A_{1}, A_{2}, \ldots, A_{N}$.
Each of the next $Q$ lines contains three space-separated integers $x_{1}$, $x_{2}$ 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 ≤ A_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ x_{1} < x_{2} ≤ N$
$1 ≤ y ≤ 10^{9}$

------  Subtasks ------
Subtask #1 (30 points): $N, Q ≤ 2,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
1

4 3

1 3 5 1

2 4 4

1 2 3

1 4 1
----- Sample Output 1 ------ 
2

1

2
----- explanation 1 ------ 
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 $(x_{2},y)$.
- For the third query, the beam collides with the $1$-st line segment and the $3$-rd line segment.

Source: codechef | Difficulty: VERY_HARD
Tags: Geometry

Sweep line algorithms

Range queries

Segment trees revisited

Data structures


Solutions:
from sys import stdin, stdout
import math

def update(bit, n, pos, v):
	pos += 1
	while pos <= n:
		bit[pos] += v
		pos += -pos & pos
	return

def getsum(bit, i):
	su = 0
	while i > 0:
		su += bit[i]
		i -= -i & i
	return su

def main():
	try:
		(n, nQ) = In()
		bit = [0] * (n + 1)
		l = list(In())
		task = []
		for i in range(n - 1):
			task.append([min(l[i], l[i + 1]), 1, i])
			task.append([max(l[i], l[i + 1]), 3, i])
		Q = []
		ans = [0 for x in range(nQ)]
		for q in range(nQ):
			(l, r, y) = In()
			l -= 1
			r -= 1
			Q.append([l, r])
			task.append([y, 2, q])
		task.sort(key=lambda x: [x[0], x[1]])
		for x in task:
			if x[1] == 1:
				update(bit, n, x[2], 1)
			elif x[1] == 3:
				update(bit, n, x[2], -1)
			else:
				ans[x[2]] = getsum(bit, Q[x[2]][1]) - getsum(bit, Q[x[2]][0])
		for x in ans:
			print(x)
	except:
		pass

def add(a, b, c):
	res = a + b
	if res >= c:
		return res - c
	else:
		return res

def mod(a, b, c):
	res = a * b
	if res >= c:
		return res % c
	else:
		return res

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	w = a // gcd(a, b)
	return w * b

def expo(a, b):
	(x, y) = (1, a)
	while b > 0:
		if b & 1:
			x = x * y
		y = y * y
		b >>= 1
	return x

def power(a, b, m):
	(x, y) = (1,)
	while b > 0:
		if b & 1:
			x = mod(x, y, m)
		y = mod(y, y, m)
		b >>= 1
	return x

def L():
	return list(map(int, stdin.readline().split()))

def In():
	return map(int, stdin.readline().split())

def I():
	return int(stdin.readline())
P = 1000000007
for _ in range(I()):
	main()


def read_int():
	return int(input().strip())

def read_int_array():
	return map(int, input().strip().split())

def update(v, i, x):
	while i < len(v):
		v[i] += x
		i += i & -i

def query(v, i):
	s = 0
	i -= 1
	while i > 0:
		s += v[i]
		i -= i & -i
	return s
for t in range(read_int()):
	(n, q) = tuple(read_int_array())
	events = []
	points = tuple(read_int_array())
	x = []
	v = [0 for i in range(n)]
	res = [0 for i in range(q)]
	for i in range(0, n - 1):
		y1 = min(points[i], points[i + 1])
		y2 = max(points[i], points[i + 1])
		events.append((y1, 1, i + 1))
		events.append((y2, 3, i + 1))
	for i in range(q):
		(x1, x2, y) = tuple(read_int_array())
		events.append((y, 2, i))
		x.append((x1, x2))
	events.sort(key=lambda x: (x[0], x[1]))
	for ev in events:
		if ev[1] == 1:
			update(v, ev[2], 1)
		elif ev[1] == 2:
			i = ev[2]
			(x1, x2) = x[i]
			res[i] = query(v, x2) - query(v, x1)
		elif ev[1] == 3:
			update(v, ev[2], -1)
	print('\n'.join(map(str, res)))


def isolateOneBit(n):
	return n & -n

def getSum(BIT, ind):
	s = 0
	num = ind
	while num > 0:
		s += BIT[num]
		num -= isolateOneBit(num)
	return s

def rangeSum(BIT, l, u):
	uSum = getSum(BIT, u)
	lSum = getSum(BIT, l - 1)
	return uSum - lSum

def updateSums(BIT, nBIT, ind, delta):
	while ind <= nBIT:
		BIT[ind] += delta
		ind += isolateOneBit(ind)

def main():
	t = int(input())
	while t:
		t -= 1
		(n, q) = map(int, input().split())
		pts = list(map(int, input().split()))
		qArr = []
		for i in range(q):
			quer = list(map(int, input().split()))
			quer.append(i)
			qArr.append(quer[:])
		ptsArr = []
		for i in range(1, n):
			a = pts[i - 1]
			b = pts[i]
			if a > b:
				(a, b) = (b, a)
			ptsArr.append((a, b, i))
		startArr = sorted(ptsArr[:])
		endArr = sorted(ptsArr[:], key=lambda x: x[1])
		qArr.sort(key=lambda x: x[2])
		fenStart = [0 for i in range(n + 10)]
		fenEnd = [0 for i in range(n + 10)]
		answers = []
		i = 0
		j = 0
		for query in qArr:
			while i < n - 1 and startArr[i][0] <= query[2]:
				updateSums(fenStart, n + 1, startArr[i][2], 1)
				i += 1
			while j < n - 1 and endArr[j][1] < query[2]:
				updateSums(fenEnd, n + 1, endArr[j][2], 1)
				j += 1
			st = rangeSum(fenStart, query[0], query[1] - 1)
			ed = rangeSum(fenEnd, query[0], query[1] - 1)
			answers.append((query[3], ed - st))
		answers.sort()
		for i in answers:
			print(-i[1])
main()


def upd(ft, i, x):
	i += 1
	while i < n:
		ft[i] += x
		i += i & -i

def qry(ft, i):
	r = 0
	while i > 0:
		r += ft[i]
		i -= i & -i
	return r

def solve():
	a = list(map(int, input().split()))
	ft = [0] * mxn
	ans = [0] * q
	(ql, qr, qy) = ([], [], [])
	for i in range(q):
		(x1, x2, y) = map(int, input().split())
		ql.append(x1 - 1)
		qr.append(x2 - 1)
		qy.append(y)
	event = []
	for i in range(0, n - 1):
		event.append((min(a[i], a[i + 1]), 1, i))
		event.append((max(a[i], a[i + 1]), 3, i))
	for i in range(q):
		event.append((qy[i], 2, i))
	event.sort()
	for (y, t, i) in event:
		if t == 1:
			upd(ft, i, 1)
		elif t == 2:
			ans[i] = qry(ft, qr[i]) - qry(ft, ql[i])
		else:
			upd(ft, i, -1)
	for i in ans:
		print(i)
mxn = 100000
n = 0
q = 0
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	solve()


def update(tree, n, i, v):
	i += 1
	while i < n:
		tree[i] += v
		i += i & -i

def query(tree, i):
	r = 0
	while i > 0:
		r += tree[i]
		i -= i & -i
	return r
t = int(input())
for _ in range(t):
	(n, q) = [int(i) for i in input().split()]
	tree = [0] * (n + 1)
	ql = []
	qr = []
	qy = []
	arr = [int(i) for i in input().split()]
	for i in range(q):
		(a, b, y1) = [int(i) for i in input().split()]
		ql.append(a - 1)
		qr.append(b - 1)
		qy.append(y1)
	events = []
	for i in range(n - 1):
		events.append((min(arr[i], arr[i + 1]), 1, i))
		events.append((max(arr[i], arr[i + 1]), 3, i))
	for i in range(q):
		events.append((qy[i], 2, i))
	events.sort()
	ans = [0] * q
	for i in events:
		if i[1] == 1:
			update(tree, n, i[2], 1)
		elif i[1] == 2:
			ans[i[2]] = query(tree, qr[i[2]]) - query(tree, ql[i[2]])
		else:
			update(tree, n, i[2], -1)
	for i in range(q):
		print(ans[i])


import numpy as np
II = lambda : [int(x) for x in input().split()]

def solve2():
	(N, Q) = II()
	A = II()
	A = np.array([A[:-1], A[1:]])
	A.sort(axis=0)
	ranges = []
	ys = []
	for q in range(Q):
		(x1, x2, y) = II()
		ranges.append((x1, x2))
		ys.append((q, y))
	ys = sorted(ys, key=lambda x: x[1])
	A_l = sorted(list(zip(A[0], range(N - 1))))
	A_r = sorted(list(zip(A[1], range(N - 1))))
	l_res = np.array([False] * (N - 1))
	r_res = np.array([True] * (N - 1))
	res = np.array([False] * (N - 1))
	results = [None] * Q
	l = 0
	r = 0
	for (q, y) in ys:
		while l < len(A_l) and y >= A_l[l][0]:
			l_res[A_l[l][1]] = True
			res[A_l[l][1]] = r_res[A_r[r][1]]
			l += 1
		while r < len(A_r) and y > A_r[r][0]:
			r_res[A_r[r][1]] = False
			res[A_r[r][1]] = False
			r += 1
		(x1, x2) = ranges[q]
		result = np.count_nonzero(res[x1 - 1:x2 - 1])
		results[q] = result
	for r in results:
		print(r)
T = int(input())
for _ in range(T):
	solve2()


def getsum(BITTree, i):
	s = 0
	i = i + 1
	while i > 0:
		s += BITTree[i]
		i -= i & -i
	return s

def updatebit(BITTree, n, i, v):
	i += 1
	while i <= n:
		BITTree[i] += v
		i += i & -i

def construct(arr, n):
	BITTree = [0] * (n + 1)
	for i in range(n):
		updatebit(BITTree, n, i, arr[i])
	return BITTree
t = int(input())
while t:
	t -= 1
	(n, q) = map(int, input().split())
	cknc = [0 for _ in range(n)]
	dawg = construct(cknc, len(cknc))
	cat = construct(cknc, len(cknc))
	final_ans = [0 for _ in range(q)]
	jake = list(map(int, input().split()))
	oooo = []
	jakex = []
	jakey = []
	for i in range(n - 1):
		jakey.append((min(jake[i], jake[i + 1]), max(jake[i], jake[i + 1]), i))
		jakex.append((min(jake[i], jake[i + 1]), max(jake[i], jake[i + 1]), i))
	jakex.sort(key=lambda x: x[0])
	jakey.sort(key=lambda x: x[1])
	loq = []
	q1 = q
	for i in range(q1):
		(x1, x2, x3) = map(int, input().split())
		x1 -= 1
		x2 -= 2
		loq.append((x1, x2, x3, i))
	loq.sort(key=lambda x: x[2])
	a = 0
	b = 0
	c = 0
	for i in range(q):
		while a < n - 1 and jakex[a][0] <= loq[i][2]:
			updatebit(dawg, n, jakex[a][2] + 1, 1)
			a += 1
		while b < n - 1 and jakey[b][1] < loq[i][2]:
			updatebit(cat, n, jakey[b][2] + 1, 1)
			b += 1
		temp1 = getsum(dawg, loq[i][1] + 1) - getsum(dawg, loq[i][0])
		temp2 = getsum(cat, loq[i][1] + 1) - getsum(cat, loq[i][0])
		final_ans[loq[i][3]] = temp1 - temp2
	for prawn in final_ans:
		print(prawn, end='\n')


def change(x, delta):
	while x <= n:
		fenwick[x] += delta
		x += x & -x

def getsum(x):
	s = 0
	while x > 0:
		s += fenwick[x]
		x -= x & -x
	return s

def change1(x, delta):
	while x <= n:
		fenwick1[x] += delta
		x += x & -x

def getsum1(x):
	s = 0
	while x > 0:
		s += fenwick1[x]
		x -= x & -x
	return s
for _ in range(int(input())):
	(m, q) = map(int, input().split())
	a = [int(o) for o in input().split()]
	a1 = []
	a2 = []
	fenwick = [0] * 150212
	fenwick1 = [0] * 150212
	n = 150212
	for i in range(m - 1):
		a1.append([min(a[i], a[i + 1]), i + 1])
		a2.append([max(a[i], a[i + 1]), i + 1])
	a1 = sorted(a1)
	a2 = sorted(a2)
	qu = []
	for i in range(q):
		(u, v, w) = map(int, input().split())
		qu.append([w, u, v - 1, i])
	qu.sort()
	i = 0
	j = 0
	ans = [0] * q
	for u in range(q):
		while j < m - 1 and a2[j][0] < qu[u][0]:
			change1(a2[j][1], 1)
			j += 1
		ans2 = getsum1(qu[u][2]) - getsum1(qu[u][1] - 1)
		while i < m - 1 and a1[i][0] <= qu[u][0]:
			change(a1[i][1], 1)
			i += 1
		ans1 = getsum(qu[u][2]) - getsum(qu[u][1] - 1)
		ans[qu[u][3]] = ans1 - ans2
	for i in ans:
		print(i)