Since we have to check which ticks are prime, we can use the Sieve of Eratosthenes to generate a list of primes. We then have to perform interwoven updates and queries, meaning that both operations must be efficient. Using traditional data structures, we can only achieve imbalanced ~\mathcal{O}(1)~ and ~\mathcal{O}(N)~ operations (with prefix sum/difference arrays), or ~\mathcal{O}(\log N)~ and ~\mathcal{O}(N \log N)~ operations (with Binary Indexed Trees or BITs). We thus have to use a range update and range query binary indexed tree that would enable ~\mathcal{O}(\log N)~ for both operation types.

We notice that, given a single range update of ~[a, b]~ by ~k~, and then a query to the sum ~S_x~ of elements in the range ~[0, x]~, there are 3 possibilities for the value of the sum:

$$\displaystyle S_x = \begin{cases} 0 & \text{if }x < a \\ k(x - (a-1)) = kx - k(a-1) & \text{if }a \le x \le b \\ k(b - (a-1)) = kb - k(a-1) & \text{if }x > b \end{cases}$$

We see that we can express this sum in the form ~\delta x - \lambda~, where ~\delta~ is the value in the array at index ~x~ after update, and ~\lambda~ is a "fix" value that we subtract in order to correct the sum. The value of ~\lambda~ varies depending on ~x~ (draw it out for better understanding):

$$\displaystyle \lambda = \begin{cases} 0 & \text{if }x < a \\ k(a-1) & \text{if }a \le x \le b \\ -kb + k(a-1) & \text{if }x > b \end{cases}$$

Showing that this idea generalizes to multiple updates and queries is left as an exercise for the reader. With this mathematical formulation, we can use 2 BITs to implement this algorithm: one to store the accumulated ~\delta~ values (which we maintain like a normal range update point query BIT), and one to store the accumulated ~\lambda~ corrections.

Or, you know, use a segment tree with lazy propagation, but the BIT solution is less clunky.

Time complexity: ~\mathcal{O}(T \log \log T + T \log N)~