## Editorial for Back To School '18: Function Maximization

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Ninjaclasher

For the first subtask, the intended solution was brute force.

Time Complexity:

For the second subtask, we can precompute for all in the range .

Then, we can create a lazy segment tree of bitsets of size , of which the bit ( indexed) of each bitset stores whether an element with value exists in either of its two children (or itself if it is a leaf node). For a query, we can handle it how it would normally be handled, except when joining two bitsets, we bitwise or them together. When performing lazy propagation on a node, we can bitshift the bitset left or right depending on the lazy value (right if the lazy value is less than , and left if it is greater than ).

Time Complexity:

For the third subtask, we can use some mathematical insight. Using Wilson's theorem, the function reduces to if is prime, or otherwise. To precompute , we can use a segmented sieve to generate the primes in the range . The rest is the same as subtask 2.

An alternative method of precomputing is to run the Miller-Rabin primality test for all in the range .

Time Complexity: or .