Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

Find count of integers in a range

Revision en1, by shoya, 2019-08-24 10:33:28

Lets say there is initially an empty array and we have to preform Q number of queries of 3 types :-
1. x, add x in the array.
2. x, delete one occurrence of x from the array if exists.
3. L R, print the count of integers present in the array in the range [L, R].

Constraints :-
- 1 <= Q <= 1e5
- L <= R
- 1 <= x, L, R <= 1e5 (small)
- 1 <= x, L, R <= 1e9 (large)

One solution that came to my mind for small constraints is to use segment tree on the range [1,1e5] with time complexity O(Q*log(1e5)) with space complexity of O(1e5). But that solution wouldn't work for large constraints.

Is there another way to solve this problem which doesn't use segtree ? Can we use c++ STL here ? Please suggest your techniques.

Also another variation to the same problem can be :-
Lets say there is initially an empty array and we have to preform Q number of queries of 3 types :-
1. x, add x in the array.
2. x, delete one occurrence of x from the array if exists.
3. x, print the count of integers present in the array greater/smaller than x.

Tags queries, problem, range query

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English shoya 2019-08-24 10:33:28 1216 Initial revision (published)