Comparing Permutations of Subarrays Problem

Revision en1, by vamaddur, 2017-07-05 10:55:21

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!

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)