The repository that contains all solutions made for the course Competitive Programming and Contests by the University of Pisa
Solved | Solution | Time |
---|---|---|
Mo Algorithm | XXXX ms | |
Segment Tree | ? ms | |
Fenwick Tree | ? ms |
The basic idea is to make a smart idea to get the range and after that we need to count how many value are smaller than
the query value.
With the Segment Tree, we can store the range inside each node, and with the fenwick tree is possible make a fenwick tree
with all 0 and make an range update from end - start
.
Time complexity of the solution is complexity: O((m + n) log n) and the space complexity: O(n))