PROBLEM LINK:Author: Sidhant Bansal DIFFICULTY:MEDIUMHARD PREREQUISITES:Persistent segment tree, polynomial hashes PROBLEM:You are given array of $n$ integers and $q$ queries. For each query you have to check if sorted elements from $[a;b]$ and $[c;d]$ have at most one mismatch on pairwise comparison. QUICK EXPLANATION:Use persistent segment tree to maintain hashes of elements which occur on each prefix. Then check if there is exactly one mismatch of hash values. EXPLANATION:In this particular problem we want to check similarity of sets of numbers so it is good idea to mark set of numbers with polynomial hash $\sum\limits_i x^{a_i}$. Since we want to check equality of hashes from subsegments, it would be useful to use wellknown technique used in $k^{th}$ order statistics or order of key on segment queries. We maintain persistent segment tree in such way that tree built over first $m$ elements of array contains number $occ_ix^i$ in $i^{th}$ leaf. Where $occ_i$ is the number of occurences of number $i$ on $m^{th}$ prefix. Now when we maintained such segment tree, we have to check whether $occ_i$ for $[a;b]$ and $[c;d]$ differ in either zero or two consequent positions:
As you can see, the code above finds both mismatch positions in $O(\log C)$. The other elegant idea to simplify the solution is to maintain sum of elements and sum of squared elements on prefixes. Then, assuming that arrays differ in numbers $p$ and $q$, we can get $pq$ and $p^2q^2$ which will give us an opportunity to find $p$ and $q$ and then simply check by hashes that corresponding segments are equal if we disregard $p$ and $q$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution will be updated soon. RELATED PROBLEMS:
This question is marked "community wiki".
asked 16 Jun '17, 11:15

Also add link to this editorial on the problem page. answered 22 Jul '17, 18:17
