I can explain what I did .please be patient :P A- rotating ball . B is ball thrown from origin.

• First I tried sending ball B at t=0. I found position of ball b at time =R (time taken by ball to reach at the circumference with thrown at time =0) if this position was in the first quadrant. Then optimal answer would be the one we get by throwing the ball B at t=0 answer in this was would be "R R%S/ gcd(R%S,S) / S/GCD(R%S,S).

• if position of ball B at t=R is not in the first quadrant then answer would be "(r/s + (r%s):1?0)*s 0/1" because he can wait for some time t>0 and then throw the ball such that it collided at R,0

In fact it is not that bad, I would not call it an overkill. Constraints are loyal, so I did the same, but using hashes.

With hashes you can compare two substrings in O(1), this gives you LCP with bin.search only, this gives you SufArray with "LCP+comparing next char" comparator; and instead of using seg.tree of pairs / two seg.trees you may use two Fenwick trees, and code becomes even simpler.

For each index i lets find such f[i], that s[i..f[i]] is unique substring, and s[i..f[i] - 1] is not. That can be done in using suffix-array and lcp. Note, that f[i] is non-decreasing sequence. Really, s[i + 1..f[i] - 1] is substring of s[i..f[i] - 1], so it is non-unique.

Now, for each query we can answer in : we'll find first segment i..f[i], which intersects with r, let it be q (q=upper_bound(f, r)). Now it's easy to count number of non-unique subsequences in s[l..r]: it's . That's because for all indicies x < q: f[x] < r, and for indicies x > q: f[x] >  = r.

May be I missed  + 1 or  - 1 somewhere, but I hope that you can get the idea.

So, O(Nlog²N) and were supposed to pass, probably your solution has an extra O(logN) factor?

Code