Изменения рейтингов за последний раунд временно удалены. Скоро они будут возвращены. ×

Efficient solution to add / sum problem

Правка en1, от Bugman, 2018-12-14 16:26:08

We have n points (xi, yi). Let both x and y be different and from [1, n].

Initially, all points have zero value.

Two types of queries:

1) add X — adding +1 to all points with xi ≤ X

2) sum Y — calculate sum of values of points with yi ≤ Y

What is best known solution? (Problem not from running contest).

Теги queries, data structures, inversions


  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Bugman 2018-12-14 16:26:08 392 Initial revision (published)