Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Given an array A consisting of N integers, you have to execute Q queries on it. These queries ask you to determine whether the two sub-arrays a to b and c to d, which are of equal length, are similar or not. The two sub-arrays a to b and c to d are said to be similar, if, after being sorted individually and then compared element by element, they have at most one mismatch. The output should be YES or NO for each query.

Note - The two sub-arrays can intersect each other and during the query process they will not affect each other in any way. 

------ Input ------ 

The first line of the input contains 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, denoting the number of elements in the array and the number of queries respectively.
The second line contains N space-separated integers - A_{1}, A_{2}, ..., A_{N} denoting the input array A. 
The next Q lines contain the queries.
The queries are given as "a b c d" (without the double quotes) where a and b are the left and right end point of the first sub-array and c and d are the left and right end point of the second sub-array. Both end points are included in a sub-array.

------ Output ------ 

For each query output "YES" or "NO" (without the double quotes) depending on whether the two sub-arrays given in that query are similar or not.

------ Constraints ------ 

a, b, c and d for the queries will always be in the range from 1 to N where a ≤ b, c ≤ d and b - a = d - c
Time limit = 2 seconds 

------ Subtasks ------ 

Subtask #1 (10 points):

$1 ≤ T ≤ 3$
$1 ≤ N, Q ≤ 10^{3}$
$1 ≤ A[i] ≤ 10^{3}$

Subtask #2 (20 points):

$1 ≤ T ≤ 3$
$1 ≤ N ≤ 10^{5}$
$1 ≤ Q ≤ 10^{4}$
$1 ≤ A[i] ≤ 10^{5}$

Subtask #3 (70 points):

$1 ≤ T ≤ 3$
$1 ≤ N, Q ≤ 10^{5}$
$1 ≤ A[i] ≤ 10^{5}$

----- Sample Input 1 ------ 
1
6 3
1 3 4 2 3 4
1 3 4 6
1 2 5 6
3 5 2 4
----- Sample Output 1 ------ 
YES
NO
YES
----- explanation 1 ------ 
In the first query the first sub-array looks like [1, 3, 4] on sorting and the second sub-array looks like [2, 3, 4] on sorting. These two sub-arrays only differ at first position so they are similar.
In the second query the first sub-array on sorting looks like [1, 3] on sorting and the second sub-array looks like [3, 4] on sorting. These two sub-arrays differ at both the positions so they are not similar.
In the third query the first sub-array look like [2, 3, 4] on sorting and the second sub-array also looks like [2, 3, 4] on sorting. Since these two sub-arrays don't differ at any position so they are similar.

Difficulty: VERY_HARD
Tags: String algorithms

Data structures

Segment trees revisited
Skill types: Data structures

Starter code:

Solutions:
def main():
	t = int(input())
	for i in range(0, t):
		(n, q) = map(int, input().split())
		arr = list(map(int, input().split()))
		sum1 = []
		sqr = []
		six = []
		s1 = 0
		s2 = 0
		s3 = 0
		for j in range(0, len(arr)):
			s1 += arr[j]
			s2 += arr[j] ** 2
			s3 += arr[j] ** 6
			sum1.append(s1)
			sqr.append(s2)
			six.append(s3)
		for k in range(0, q):
			(a, b, c, d) = map(int, input().split())
			a -= 1
			b -= 1
			c -= 1
			d -= 1
			flagres = 0
			if a > 0:
				if c > 0:
					cv1 = -sum1[a - 1] - (sum1[d] - sum1[c - 1]) + sum1[b]
					cv2 = -sqr[a - 1] - (sqr[d] - sqr[c - 1]) + sqr[b]
					cv3 = -six[a - 1] - (six[d] - six[c - 1]) + six[b]
				elif c == 0:
					cv1 = -sum1[a - 1] - sum1[d] + sum1[b]
					cv2 = -sqr[a - 1] - sqr[d] + sqr[b]
					cv3 = -six[a - 1] - sqr[d] + six[b]
			elif a == 0:
				if c > 0:
					cv1 = -(sum1[d] - sum1[c - 1]) + sum1[b]
					cv2 = -(sqr[d] - sqr[c - 1]) + sqr[b]
					cv3 = -(six[d] - six[c - 1]) + six[b]
				elif c == 0:
					cv1 = -sum1[d] + sum1[b]
					cv2 = -sum1[d] + sqr[b]
					cv3 = -sum1[d] + six[b]
			if cv1 == 0:
				if cv2 == 0 and abs(cv3) < 0.01:
					flagres = 0
				else:
					flagres = 1
			elif cv2 % cv1 == 0:
				quo = cv2 // cv1
				x = (quo + cv1) // 2
				y = (quo - cv1) // 2
				if (quo + cv1) % 2 == 0 and (quo - cv1) % 2 == 0:
					if x >= 1 and y >= 1:
						if abs(x ** 6 - y ** 6 - cv3) < 0.01:
							ta = 0
							taa = -1
							tb = 0
							tbb = -1
							for vb in range(a, b + 1):
								if arr[vb] > x:
									ta = ta + 1
								elif arr[vb] == x:
									taa = taa + 1
							for vb1 in range(c, d + 1):
								if arr[vb1] > y:
									tb = tb + 1
								elif arr[vb1] == y:
									tbb = tbb + 1
							if ta == tb:
								flagres = 0
							elif ta + taa == tb or tb + tbb == ta:
								flagres = 0
							else:
								flagres = 1
						else:
							flagres = 1
					else:
						flagres = 1
				else:
					flagres = 1
			else:
				flagres = 1
			if flagres == 0:
				print('YES')
			else:
				print('NO')
main()


import sys
import math

def main():
	T = int(input())
	for _ in range(T):
		(N, Q) = list(map(int, input().strip().split(' ')))
		A = list(map(int, input().strip().split(' ')))
		Sum = []
		sqrt = []
		square = []
		temp1 = 0
		tempq = 0
		temp2 = 0
		for i in range(len(A)):
			L = A[i]
			temp1 += L
			temp2 += L ** 2
			tempq += L ** 6
			Sum += [temp1]
			square += [temp2]
			sqrt += [tempq]
		for jj in range(Q):
			(a, b, c, d) = list(map(int, input().strip().split(' ')))
			a = a - 1
			b = b - 1
			c = c - 1
			d = d - 1
			if a > 0 and c > 0:
				T1 = Sum[b] - Sum[a - 1] - (Sum[d] - Sum[c - 1])
				T2 = square[b] - square[a - 1] - (square[d] - square[c - 1])
				Tq = sqrt[b] - sqrt[a - 1] - (sqrt[d] - sqrt[c - 1])
			elif a > 0 and c == 0:
				T1 = Sum[b] - Sum[a - 1] - Sum[d]
				T2 = square[b] - square[a - 1] - square[d]
				Tq = sqrt[b] - sqrt[a - 1] - sqrt[d]
			elif a == 0 and c > 0:
				T1 = Sum[b] - (Sum[d] - Sum[c - 1])
				T2 = square[b] - (square[d] - square[c - 1])
				Tq = sqrt[b] - (sqrt[d] - sqrt[c - 1])
			elif a == 0 and c == 0:
				T1 = Sum[b] - Sum[d]
				T2 = square[b] - square[d]
				Tq = sqrt[b] - sqrt[d]
			if T1 == 0:
				if T2 == 0 and abs(Tq) < 0.01:
					print('YES')
				else:
					print('NO')
			elif T2 % T1 == 0:
				TTT = T2 // T1
				x = (TTT + T1) // 2
				y = (TTT - T1) // 2
				if (TTT + T1) % 2 == 0 and (TTT - T1) % 2 == 0:
					if x >= 1 and y >= 1:
						if abs(x ** 6 - y ** 6 - Tq) < 0.01:
							temp1 = 0
							temp11 = -1
							temp2 = 0
							temp22 = -1
							for i in range(a, b + 1):
								if A[i] > x:
									temp1 += 1
								elif A[i] == x:
									temp11 += 1
							for i in range(c, d + 1):
								if A[i] > y:
									temp2 += 1
								elif A[i] == y:
									temp22 += 1
							if temp1 == temp2:
								print('YES')
							elif temp1 + temp11 == temp2 or temp2 + temp22 == temp1:
								print('YES')
							else:
								print('NO')
						else:
							print('NO')
					else:
						print('NO')
				else:
					print('NO')
			else:
				print('NO')
main()