I ran into a clever trick while reading the solutions here https://codeforces.me/blog/entry/133382 (look at problem 2006C, "Implementation — Two Pointers")↵
↵
The problem is: let's say there's an array $a$ and an associative operation ${*}$ and we are interested in computing ${f(l, r) := a_l * a_{l+1} * \ldots * a_r}$ , where we want to be able to increment $l$ or $r$ and easily recompute $f$. If we can do that, then we can solve all kinds of two-pointer-style problems.↵
↵
If $f$ is invertible, e.g. addition, we can easily do this by just keeping track of a single aggregated value. But what if $f$ is something like $\gcd$? In this case, this simple solution won't work. But there is a trick.↵
↵
With the simple solution, the hard part is incrementing $l$ because if we only keep the aggregated value for $f(l, r)$, we can't recover the value for $f(l+1, r)$. To do that we would ideally need to keep a list of values $f(l, r), f(l+1, r), \ldots, f(r,r)$ and then incrementing $l$ would just involve popping the front of the list. But then, incrementing $r$ is hard because we'd need to recompute the whole list.↵
↵
To combine these two approaches, we keep $f(l, m), f(l+1, m), \ldots, f(m, m)$ for some intermediate $m$, and also $f(m+1, r)$. In the beginning, $l=m=r=0$ . Then:↵
↵
- to increment $r$ we simply recompute the tail value by taking $f(m+1, r+1)=f(m+1, r) * a_{r+1}$↵
- to increment $l$:↵
- if $l < m$ we pop the list.↵
- otherwise, $l = m$. We set $m := r$, and recompute the whole list from $l$ to $r$. This may seem slow but the subarrays recomputed in this manner don't overlap and therefore this has amortized constant cost.↵
- to query $f(l, r)$ we simply compute $f(l, m) * f(m+1, r)$.↵
- EDIT: we can decrement l too! Just compute $f(l-1, m)$ and push to the front of the list. This doesn't break the amortized performance because we never decrement $m$.↵
↵
That's it!↵
↵
Note that this requires weonlynever increment the bounds, which is useful only for some$r$, so it doesn't fit every problems.↵
↵
Does this trick have a name? Is it "lore"? I haven't seen it before. But it's been a while since I've done a contest (hard to find time these days...) so maybe it's already well known. For those who haven't seen it, hopefully you find it interesting!↵
↵
The problem is: let's say there's an array $a$ and an associative operation ${*}$ and we are interested in computing ${f(l, r) := a_l * a_{l+1} * \ldots * a_r}$ , where we want to be able to increment $l$ or $r$ and easily recompute $f$. If we can do that, then we can solve all kinds of two-pointer-style problems.↵
↵
If $f$ is invertible, e.g. addition, we can easily do this by just keeping track of a single aggregated value. But what if $f$ is something like $\gcd$? In this case, this simple solution won't work. But there is a trick.↵
↵
With the simple solution, the hard part is incrementing $l$ because if we only keep the aggregated value for $f(l, r)$, we can't recover the value for $f(l+1, r)$. To do that we would ideally need to keep a list of values $f(l, r), f(l+1, r), \ldots, f(r,r)$ and then incrementing $l$ would just involve popping the front of the list. But then, incrementing $r$ is hard because we'd need to recompute the whole list.↵
↵
To combine these two approaches, we keep $f(l, m), f(l+1, m), \ldots, f(m, m)$ for some intermediate $m$, and also $f(m+1, r)$. In the beginning, $l=m=r=0$ . Then:↵
↵
- to increment $r$ we simply recompute the tail value by taking $f(m+1, r+1)=f(m+1, r) * a_{r+1}$↵
- to increment $l$:↵
- if $l < m$ we pop the list.↵
- otherwise, $l = m$. We set $m := r$, and recompute the whole list from $l$ to $r$. This may seem slow but the subarrays recomputed in this manner don't overlap and therefore this has amortized constant cost.↵
- to query $f(l, r)$ we simply compute $f(l, m) * f(m+1, r)$.↵
- EDIT: we can decrement l too! Just compute $f(l-1, m)$ and push to the front of the list. This doesn't break the amortized performance because we never decrement $m$.↵
↵
That's it!↵
↵
Note that this requires we
↵
Does this trick have a name? Is it "lore"? I haven't seen it before. But it's been a while since I've done a contest (hard to find time these days...) so maybe it's already well known. For those who haven't seen it, hopefully you find it interesting!↵
