How can (<*) be implemented optimally for sequences?

Question

The Applicative instance for Data.Sequence generally performs very well. Almost all the methods are incrementally asymptotically optimal in time and space. That is, given fully forced/realized inputs, it's possible to access any portion of the result in asymptotically optimal time and memory residency. There is one remaining exception: (<*). I only know two ways to implement it as yet:

1. The default implementation

    xs <* ys = liftA2 const xs ys
   

   This implementation takes O(|xs| * |ys|) time and space to fully realize the result, but only O(log(min(k, |xs|*|ys|-k))) to access just the kth element of the result.

2. A "monadic" implementation

    xs <* ys = xs >>= replicate (length ys)
   

   This takes only O(|xs| * log |ys|) time and space, but it's not incremental; accessing an arbitrary element of the result requires O(|xs| * log |ys|) time and space.

I have long believed that it should be possible to have our cake and eat it too, but I've never been able to juggle the pieces in my mind well enough to get there. To do so appears to require a combination of ideas (but not actual code) from the implementations of liftA2 and replicate. How can this be done?

---

Note: it surely won't be necessary to incorporate anything like the rigidify mechanism of liftA2. The replicate-like pieces should surely produce only the sorts of "rigid" structures we use rigidify to get from user-supplied trees.

Update (April 6, 2020)

Mission accomplished! I managed to find a way to do it. Unfortunately, it's a little too complicated for me to understand everything going on, and the code is ... rather opaque. I will upvote and accept a good explanation of what I've written, and will also happily accept suggestions for clarity improvements and comments on GitHub.

Update 2

Many thanks to Li-Yao Xia and Bertram Felgenhauer for helping to clean up and document my draft code. It's now considerably less difficult to understand, and will appear in the next version of containers. It would still be nice to get an answer to close out this question.