PROBLEM LINK:
Author: Denis Anischenko
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
None (though knowledge of sparse table may be helpful for understanding)
PROBLEM:
Given a non-changing array, answer queries of the form “? l r: what is \prod\limits_{i=l}^{r} a_i modulo P (P is not necessarily prime)?” (subarray product query). The queries are online, and the constraints are so tight that an O(1) per query solution is required.
QUICK EXPLANATION:
The intended solution does not utilize the fact that the query operation is product modulo P. The proposed data structure is capable of handling any associative operation query on subarray in O(1) (online, provided that the array is not changing).
The idea of the intended data structured is somewhat similar to the idea of a sparse table: we will precompute the operation results on some subarrays of the array so that every input query subarray can be represented as a union of constant (at most 2) number of subarrays we already know the answer for. However, the difference with the classic sparse table (used for static RMQ problem) is that the given operation \bigoplus is not idemptotent: a\bigoplus a\neq a for the most of a's, so the union we will use must be disjoint. The operation is also not invertible, so we can’t use the prefix-sums approach.
For each k=1,\ldots,\lceil \log_2 N\rceil consider all indices of the array that are divisible by 2^k as “pivots”. Precompute the product on subarrays whose left or right bound is a “pivot”, and that do not contain any other pivots.
Claim: for each [l,r] query we can choose pivot element 2^k\cdot x in such way that we already precomputed the operation for some subarray with indices [l, 2^k\cdot x), [2^k\cdot x, r].
EXPLANATION:
Build the following data structure: for each k=1,\ldots,\lceil \log_2 N\rceil, for each i=0,1,\ldots,N-1 (we use 0-indexation of the array) compute (we omit modulo P for simplicity; assume that all integers are members of the ring \mathbb{Z}_P, with multiplication defined accordingly):
A_{k,i}=\prod\limits_j a_j\text{ for }\left\lfloor\dfrac{i}{2^k}\right\rfloor\cdot 2^k\le j\le i
B_{k,i}=\prod\limits_j a_j \text{ for }i\le j \le \left\lceil\dfrac{i+1}{2^k}\right\rceil\cdot 2^k-1
Here \text{~} denotes bitwise negation, \& denotes bitwise AND operation.
The meaning of the expressions is the following:
-
\left\lfloor\dfrac{i}{2^k}\right\rfloor\cdot 2^k is the largest number not exceeding i that is divisible by 2^k. Implementation-wise, this number I is characterized by the property I~\&~ 2^k=0 (\& denotes bitwise AND).
-
\left\lceil\dfrac{i+1}{2^k}\right\rceil\cdot 2^k-1 is by one less than the smallest number more than i that is divisible by 2^k. Implementation-wise, this number J is characterized by the property J\& 2^k=2^k-1 (\& denotes bitwise AND).
Let’s notice the following: suppose we have a query [L, R], L\neq R, and for selected k the range of indices [L+1, R] contains unique index I divisible by 2^k. Then
Indeed, if that index of the form I=2^k\cdot x\in[L+1, R] exists and is unique, then, by the meaning of the corresponding expressions above:
I=\left\lfloor\dfrac{R}{2^k}\right\rfloor\cdot 2^k
I=\left\lceil\dfrac{L+1}{2^k}\right\rceil\cdot 2^k
And by definition of B_{k,L} and A_{k,R}:
Can we find the k for which I is unique? Surely, such k exists because if for some k there are X>1 indices divisible by 2^k in the range [L+1,R], for k+1 there are \dfrac{X}{2} such indices if X is even and either \left\lfloor\dfrac{X}{2}\right\rfloor or \left\lceil\dfrac{X}{2}\right\rceil if X is odd. Incrementing k sufficient number of times we arrive to X=1.
It remains to notice that k can be chosen as k=\max\limits_l: 2^l\le L\oplus R (\oplus denotes bitwise XOR).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
