EDYOOCATIONAL CONTESNT #2

Правка en1, от mahmoud_osama08, 2024-03-29 16:41:52

Today we teach the ability to perform range queries in $$$\mathcal{O}(1)$$$, regardless of the query rekwaired.

Consider $$$Q = [l, r]$$$.

Iterate over all quadraubles $$$\left(a,b,c,d\right)$$$, add $$$Q[a]\times Q[b]\times Q[c] - Q[d]^2$$$

Now to solve single qwery, output $$$\text{Quadruble}[l][r^2][r-l^r][l+r^l]$$$.

The precomputation took $$$\mathcal{O}(1)$$$ time because $$$a,b,c,d\le 10^{18}$$$, a constant

You solve every query in $$$\mathcal{O}(1)$$$ cuz u immediately output the formula.

if you dont trust me, try it in this problem

you can see that my code is fastest ($$$0.00$$$ s)

Теги range queries, segment tree, educational, red

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский mahmoud_osama08 2024-03-29 16:41:52 646 Initial revision (published)