For each broadcasting radio frequency ~x~, we can keep track of two other radio frequencies ~L_x~ and ~R_x~, the next smallest and the next largest broadcasting frequency which makes noise with ~x~ (if ~L_x~ doesn't exist, we take it to be ~-1~, and if ~R_x~ doesn't exist, we take it to be ~10^9~). The interval ~[l, r]~ creates noise if ~\max_{x \in [l,r]} L_x \ge l~ or ~\min_{x \in [l,r]} R_x \le r~. The minimum and maximum in the interval can be determined in ~\mathcal O(\log n)~ using a segment tree. What remains is to figure out a way to keep track of ~L_x~ and ~R_x~.

Notice that two frequencies create noise if and only if they are both divisible by some prime number. If in the sieve of Eratosthenes, we store for each number one of its prime factors, then we can factor a number in ~\mathcal O(\log n)~ by going over each of its prime factors. For each prime, we can maintain a set of broadcasting frequencies divisible by this prime. Then for each frequency, there are at most ~\mathcal O(\log n)~ candidates for ~L_x~ and ~R_x~.

These observations are sufficient to obtain a solution. When a frequency ~x~ becomes active, for each prime factor of ~x~, we look at the set of broadcasting frequencies for that prime and we find the next smallest and next largest frequency in this set. The minimum of the larger frequencies will be ~R_x~, and the maximum of the smaller frequencies will be ~L_x~. Additionally, for each of the ~L_x~ and ~R_x~ candidates, their ~L~ and ~R~ values might change, so we must update them. The number of candidates is ~\mathcal O(\log n)~, and updating ~L_x~ or ~R_x~ takes ~\mathcal O(\log n)~. Therefore, we can keep track of the updates in ~\mathcal O(\log^2 n)~. When deactivating a frequency, we do the opposite. We erase the number ~x~ from all the sets it is in, and adjust ~L_x~ and ~R_x~ of its neighbours. Again, the number of neighbours is ~\mathcal O(\log n)~.

It should be noted that the time complexity is in practice even better because numbers less than ~10^6~ can have at most ~7~ distinct prime factors since ~2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 > 10^6~.