Hackerrank "Almost Equal" solution
Constraints
    1 &lt;= N &lt;= 100000
    0 &lt;= K &lt;= 109
    0 &lt;= H[i] &lt;= 109
    1 &lt;= Q &lt;= 100000
    0 &lt;= l &lt;= r &lt; N
  


My rule of thumb for this kind of challenge is that 109 operations is a limit. So, ignoring the hidden constant of Landau notation, we're looking at something which is \$O(N\sqrt N + Q\sqrt Q + Q\sqrt{N} + K)\$. In particular, each query shouldn't take more than \$\sqrt N\$ time. That would seem to push us towards a preprocessing step which is \$O(N\sqrt N + K)\$ and which allows us to process individual queries fast. Alternatively, we might have a preprocessing step which takes into account the queries, but that's likely to be more complicated.

Since your approach takes (in the worst case) \$O(QN\lg N)\$ time, it's definitely nowhere near complying with my rule of thumb.



If we consider first the idea of a preprocessing step which takes into account the queries, it's quite easy to construct a really nasty case where we have boundaries between every consecutive pair of wrestlers, and each one contributes to multiple queries. E.g. take the following 100000 queries:

(0, 99999), (1, 99998), (2, 99997), ..., (49999,50000),
(0, 49999), (1, 50000), (2, 50001), ..., (49999, 99998)


I don't find that approach promising.



Ideas which might be more promising are bucketing the wrestlers in buckets of width \$K\$, so that each wrestler can only interact with those in the same bucket and some of those in the adjacent buckets - although the "some of" is a problem; and inclusion-exclusion, although I can't quite get that to work. It's "fast enough" to precompute tables \$C[a]\$ which is the number of valid fights between \$i \le a &lt; j\$; \$L[a]\$ which is the number of valid fights between \$i &lt; j \le a\$; and \$R[a]\$ which is the number of valid fights between \$a \le i &lt; j\$. But the closest I can get to the number of valid fights between \$l \le i &lt; j \le r\$ is the difference of that with the number of valid fights between \$i \le l\$ and \$j \ge r\$.