Subtask 1

For this subtask, there are no modifications. For every colour ~c~, we can order all pens of that colour by their prettiness. Let ~m_c~ be the ID of the pen with the highest (maximum) prettiness value with colour ~c~ and let ~s_c~ be ID of the second highest. Note that ~s_c~ may not exist for some ~c~.

If we do not change any pen's colour, then the answer is $$\displaystyle \sum_{i = 1}^M P_{m_i}$$ where ~P_{k}~ is the prettiness of pen with ID ~k~. This can be stored in a variable and used for further calculations. Observe that we can always achieve the optimal answer by only changing the colour of ~s_c~. And the resulting answer if we change ~s_c~ to have colour ~d~ is $$\displaystyle \left(\sum_{i = 1}^M P_{m_i}\right) - P_{m_d} + \max(P_{m_d}, P_{s_c})$$ However, we cannot afford to try to change the colour of every pen ~s_c~ to every colour ~d~ as there are up to ~M^2~ different ~(c, d)~ pairs to considers. However, we can notice that it is always optimal to pick the colours with the smallest ~P_{m_c}~ or second smallest ~P_{m_c}~. This reduces to ~2M~ pairs to check, which will run in time. This solution runs in ~\mathcal{O}(N)~ time.

Subtask 2

There is only 1 colour for this subtask. Thus, the answer is the pen with the largest prettiness. Because there are updates, we can maintain this information in a dynamic data structure such as a balanced binary search tree (BBST) such as std::set<std::pair<int, int>> (the pair represents a pen by its prettiness and pen ID) or with a std::multiset<int> in C++ where the pens are ordered by their prettiness. To update, we also need a mapping from pen ID to their prettiness, which can be stored in an array. If implemented correctly, this runs in ~\mathcal{O}((N + Q) \log N)~ time.

Subtask 3

Now the pens could be of 2 colours. Notice that we are always able to pick any two pens. Thus, we can always pick the two pens with the highest prettiness values. We employ a similar solution to the second subtask by maintaining the appropriate data structures and summing the two highest prettiness values instead of just taking the highest prettiness value. This runs in the same time as the intended Subtask 2 solution, ~\mathcal{O}((N + Q) \log N)~ time.

Subtask 4

Now, there can be up to 10 colours. Here, we can solve this by using Subtask 1's observations and Subtask 3's data structures by applying Subtask 1 to every query. This results in a time complexity of ~\mathcal{O}((N + QM) \log N)~.

Subtask 5

This subtask was meant to award contestants with the correct idea as Subtask 6, even if they have implemented parts incorrectly.

Subtask 6

For the final subtask, we can further reduce the ~2M~ pairs to check to two cases:

• We change the colour of no pens.
• We change the colour of the ~s_c~ with the largest ~P_{s_c}~ to the colour of ~m_d~ with the smallest ~P_{m_d}~.

Note that the ~s_c~ with the largest prettiness is the same as the pen that is not a ~m_c~ with the largest prettiness. We can find ~s_c~ with largest ~P_{s_c}~ and pen ~m_d~ with smallest ~P_{m_d}~ by having these data structures and values:

• A BBST of the pens of the form ~m_c~ ordered by prettiness
• A BBST of every other pen, which is not a ~m_c~ ordered by prettiness
• A BBST for every colour ~c~, storing every pen of the same colour ~c~ ordered by prettiness
• An array of pens storing their prettiness and colour, indexed-by their ids
• A value representing the sum of prettiness of the first BBST (Let this value be ~T~)

After every query, we must quickly update all data structures. Now the answer is $$\displaystyle \max(T, T - \text{smallest prettiness of the first BBST} + \text{largest prettiness of the second BBST})$$ If all the data structures are maintained properly, this solution runs in ~\mathcal{O}((N + Q) \log N)~ time.