Comparing Permutations of Subarrays Problem

Revision en3, by vamaddur, 2017-07-06 12:14:20

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 2 seconds, as expected.

UPD2: Original problem statement is here.

Tags offline query, segment tree, permutation, subarray


  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)