I solved it using bitsets.
For each N, calculate the intervals it belongs to and make a bitset corresponding to the index of the interval.
For the given example.
- interval 0 = (4 5)
- interval 1 = (3 5)
- interval 2 = (2 4)
- interval 3 = (1 3)
- interval 4 = (5 5)
The bitsets for each N would be
- 00010
- 00110
- 01110
- 11100
- 11001
Now for each element in the query cumulatively xor all the bitsets. And at the last count all the bits that are set. This would give the number of intervals that contain odd number of integers.
I read somewhere bitset uses some hashing mechanism to compute the operations. Thus this passes. If testcases could be made so that hashing collides most of the times, this won’t work, as it would take O(n) to only count the number of bits set.