Comparing Permutations of Subarrays Problem
Difference between en2 and en3, changed 81 character(s)
We are given an array of size N and Q queries (1 <= N, Q <= 100000). Each query has 4 parameters: index i, index j, length L, and differences D (0 <= D <= 1). We must answer "YES" if a permutation of the subarray from arr[i] to arr[i+L-1] differs from a permutation of the subarray from arr[j] to arr[j+L-1] in at most D places, and "NO" otherwise.↵

This sounds like an offline segment tree problem, but I am not sure how to start implementing it.↵

Can someone give me some hints to get me started and moving in the right direction?↵

Please help, and thanks in advance!↵

UPD: Just for the sake of it, I tried submitting a naive N^2 solution, which didn't make it in the time limit of 
12 seconds, as expected.

UPD2: Original problem statement is [here](https://pastebin.com/AWh51K8M).

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English vamaddur 2017-07-06 12:14:20 81
en2 English vamaddur 2017-07-06 08:17:07 139
en1 English vamaddur 2017-07-05 10:55:21 618 Initial revision (published)