Cloning

All submissions for this problem are available.
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 subarrays a to b and c to d, which are of equal length, are similar or not. The two subarrays 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 subarrays 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 spaceseparated 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 subarray and c and d are the left and right end point of the second subarray. Both end points are included in a subarray.
Output
For each query output "YES" or "NO" (without the double quotes) depending on whether the two subarrays 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  cTime 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}
Example
Input: 1 6 3 1 3 4 2 3 4 1 3 4 6 1 2 5 6 3 5 2 4 Output: YES NO YES
Explanation
In the first query the first subarray looks like [1, 3, 4] on sorting and the second subarray looks like [2, 3, 4] on sorting. These two subarrays only differ at first position so they are similar.
In the second query the first subarray on sorting looks like [1, 3] on sorting and the second subarray looks like [3, 4] on sorting. These two subarrays differ at both the positions so they are not similar.
In the third query the first subarray look like [2, 3, 4] on sorting and the second subarray also looks like [2, 3, 4] on sorting. Since these two subarrays don't differ at any position so they are similar.
Author:  sidhant007 
Tags  june17, mediumhard, polynomial, segmenttree, sidhant007 
Date Added:  10052017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions