shoya's blog

By shoya, history, 4 weeks ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

click, or if it can be solved offline you can just compress the numbers.