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 1 second, as expected.
↵
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 1 second, as expected.
