This is a well known technique, but I couldn't find almost any detailed tutorial, so I'll try to help with this one.↵
↵
####Motivational Problem: ↵
↵
You have an array $A$ and $Q$ queries, which are, say if the subarray from $l$ to $r$, ($A[l]$, $A[l+1]$, $...$, $A[r]$) forms a permutation.↵
↵
####Some basic observations:↵
↵
Only the set of elements matters, the order is irrelevant.↵
↵
You want to know if each element is exactly once.↵
↵
####Solution:↵
↵
Assign a random number $randval[i]$ to each number $i$, now we can say that if the XOR of the subarray ( $randval[A[l]]$ xor $randval[A[l+1]]$ xor $...$ xor $randval[A[r]]$ ) is equal to the xor of any permutation of size $r - l + 1$ (for example $1$, $2$, $3$, ... ,$r-l+1$, which hash is $randval[1]$ xor $randval[2]$ xor $...$ xor $randval[r-l+1]$ ) the subarray is a permutation.↵
↵
####Some Insights:↵
↵
With the XOR we have some issues, we are counting if the number of occurrences of each element is even or odd, not the real number of occurrences, however in this problem if we had repeated elements the XOR-hash will never be the same than the XOR-hash of $1$, $2$, $3$, ... ,$r-l+1$, because if we have some numbers more than once, since there are only $r - l + 1$ numbers in the subarray, and also $r - l + 1$ numbers are needed to form the permutation, some of them cannot appear.↵
↵
As an alternative to this technique we can use polynomial hash over a binary string that represents the occurrences of each element modulo $2$ ($x$-character of this string represents the number of occurrences of $x$ modulo $2$), but with XOR hash we can do it faster, with less code and case handling, and with less care about collisions and hacks.↵
↵
With bitwise-OR we count the number of occurrences of each element of the set modulo $2$, if we use $k$-nary xor we will count the number of occurrences modulo $k$.↵
↵
####Collisions:↵
↵
Now it's time to talk about collisions, as the numbers are random, the probability of collision in each query if we had only $1$ bit will be about $1/2$. And since XOR is independent on each bit, if we use k bits, the probability of collision in each query is $2^{-k}$. We can use 32-bit random integers or 64-bit random integers depending on the number of queries required. Since the numbers are generated randomly, I think this hashing can't be hacked, but I am not sure, if someone knows more about this, please send some feedback.↵
↵
####More problems using this technique (in no particular order of difficulty):↵
↵
[F. The Number of Subpermutations from Educational Codeforces Round 66](https://codeforces.net/problemset/problem/1175/F) Here editorial doesn't use it, but I have one solution with this technique.↵
↵
<spoiler summary="Quick explanation (spoiler)">↵
Let's think about divide and conquer, we have a function $f(l,r)$ which counts all permutations from $l$ to $r$, which consists of the following steps:↵
↵
First, select the index of maximum element between $l$ and $r$, then loop over the smallest of the ranges $[l,indexofmaxelement)$ and $(indexofmaxelement,r]$, and for each $i$, add to a vector (which stores all possible permutations) the subarray that has length $maxelement$ if it includes $indexofmaxelement$ and starts (or ends if we are looping over the right side) at $i$, after this, call $f(l,indexofmaxelement-1)$ and $f(indexofmaxelement+1,r)$. Note that all possible permutations will be added to the vector with this function and because of we always loop over the smallest part, it will add at most $O(n\log{n})$ queries, which can be answered with the algorithm explained above in this tutorial.↵
</spoiler>↵
↵
[E. The Untended Antiquity from Codeforces Round #439 Div 2](https://codeforces.net/problemset/problem/869/E)↵
↵
[G. Three Occurrences from Educational Codeforces Round 95](https://codeforces.net/problemset/problem/1418/G)↵
↵
[C. Square Subsets from Codeforces Round #448 Div 2](https://codeforces.net/contest/895/problem/C) but if we had just 40 numbers up to 10^6.↵
↵
Feel free to send any feedback.↵
↵
####Motivational Problem: ↵
↵
You have an array $A$ and $Q$ queries, which are, say if the subarray from $l$ to $r$, ($A[l]$, $A[l+1]$, $...$, $A[r]$) forms a permutation.↵
↵
####Some basic observations:↵
↵
Only the set of elements matters, the order is irrelevant.↵
↵
You want to know if each element is exactly once.↵
↵
####Solution:↵
↵
Assign a random number $randval[i]$ to each number $i$, now we can say that if the XOR of the subarray ( $randval[A[l]]$ xor $randval[A[l+1]]$ xor $...$ xor $randval[A[r]]$ ) is equal to the xor of any permutation of size $r - l + 1$ (for example $1$, $2$, $3$, ... ,$r-l+1$, which hash is $randval[1]$ xor $randval[2]$ xor $...$ xor $randval[r-l+1]$ ) the subarray is a permutation.↵
↵
####Some Insights:↵
↵
With the XOR we have some issues, we are counting if the number of occurrences of each element is even or odd, not the real number of occurrences, however in this problem if we had repeated elements the XOR-hash will never be the same than the XOR-hash of $1$, $2$, $3$, ... ,$r-l+1$, because if we have some numbers more than once, since there are only $r - l + 1$ numbers in the subarray, and also $r - l + 1$ numbers are needed to form the permutation, some of them cannot appear.↵
↵
As an alternative to this technique we can use polynomial hash over a binary string that represents the occurrences of each element modulo $2$ ($x$-character of this string represents the number of occurrences of $x$ modulo $2$), but with XOR hash we can do it faster, with less code and case handling, and with less care about collisions and hacks.↵
↵
With bitwise-OR we count the number of occurrences of each element of the set modulo $2$, if we use $k$-nary xor we will count the number of occurrences modulo $k$.↵
↵
####Collisions:↵
↵
Now it's time to talk about collisions, as the numbers are random, the probability of collision in each query if we had only $1$ bit will be about $1/2$. And since XOR is independent on each bit, if we use k bits, the probability of collision in each query is $2^{-k}$. We can use 32-bit random integers or 64-bit random integers depending on the number of queries required. Since the numbers are generated randomly, I think this hashing can't be hacked, but I am not sure, if someone knows more about this, please send some feedback.↵
↵
####More problems using this technique (in no particular order of difficulty):↵
↵
[F. The Number of Subpermutations from Educational Codeforces Round 66](https://codeforces.net/problemset/problem/1175/F) Here editorial doesn't use it, but I have one solution with this technique.↵
↵
<spoiler summary="Quick explanation (spoiler)">↵
Let's think about divide and conquer, we have a function $f(l,r)$ which counts all permutations from $l$ to $r$, which consists of the following steps:↵
↵
First, select the index of maximum element between $l$ and $r$, then loop over the smallest of the ranges $[l,indexofmaxelement)$ and $(indexofmaxelement,r]$, and for each $i$, add to a vector (which stores all possible permutations) the subarray that has length $maxelement$ if it includes $indexofmaxelement$ and starts (or ends if we are looping over the right side) at $i$, after this, call $f(l,indexofmaxelement-1)$ and $f(indexofmaxelement+1,r)$. Note that all possible permutations will be added to the vector with this function and because of we always loop over the smallest part, it will add at most $O(n\log{n})$ queries, which can be answered with the algorithm explained above in this tutorial.↵
</spoiler>↵
↵
[E. The Untended Antiquity from Codeforces Round #439 Div 2](https://codeforces.net/problemset/problem/869/E)↵
↵
[G. Three Occurrences from Educational Codeforces Round 95](https://codeforces.net/problemset/problem/1418/G)↵
↵
[C. Square Subsets from Codeforces Round #448 Div 2](https://codeforces.net/contest/895/problem/C) but if we had just 40 numbers up to 10^6.↵
↵
Feel free to send any feedback.↵
