First, consider the problem without any updates to the list. While there are many ways to interpret this problem, one way is to recognize that it is a variation of the bounded knapsack problem, which itself can be transformed into the 0-1 knapsack problem. Here, the weight of an item is the fuel for the route, and the value of an item is the cash earned for each repeated completion. Each item is duplicated ~\mathcal O(\log K)~ times, such that each of the duplicated items represents the original item repeated ~x~ times where ~x~ is a distinct power of ~2~, such that the sum of ~x~ for all of the duplicated items is equal to ~K~ (there may need to be one item where ~x~ is not a power of ~2~). The standard 0-1 knapsack algorithm can then be performed. In order to deal with the different cash value earned for the first completion, we can solve the bounded knapsack problem for ~K - 1~ items, and perform 0-1 knapsack on a single item. The maximum value for a weight ~j~ for the first ~i~ routes can be updated as usual, with the exception that the dynamic programming now becomes ~dp[i][j] = \max(dp[i - 1][j], dp2[j - f_i] + a_i)~ where ~dp[i][j]~ is the maximum cash earned for the first ~i~ routes using at most ~j~ fuel, and ~dp2[j]~ is the maximum cash earned for the first ~i~ items and completing route ~i~ up to ~K - 1~ times, each earning ~b_i~ cash.

Side Note: Bounded knapsack can be performed in ~\mathcal O(N \cdot F \cdot \log K)~ time. There is a method that can solve this in ~\mathcal O(N \cdot F)~ time, however it is unnecessary for this problem.

To solve the problem with updates, we can see that the versions of the app form a rooted directed tree, where the vertices are the versions of the app, and the edges are from the old version to the new version of the app. If we treat each update as a removal of an item, followed by an addition of an item to the knapsack, we can flatten the tree into an Euler Tour, to have a linear progression of changes.

Observe that we can undo the addition of the most recent item to the knapsack easily by removing the last row of the dynamic programming. Thus, if there is some reorganization of the ordering of the removals and additions, then the problem can be solved more easily. We can use a divide and conquer approach to reorder the addition of items. We can treat an item as being active for a certain interval of time. For a time interval of ~[l, r]~ with ~m = (l + r) / 2~, we can first add to the knapsack all items which have one endpoint of its interval in the range ~[m + 1, r]~. Since we know these items will not be modified in the range ~[l, m]~, we can recursively solve the problem in the range ~[l, m]~. Afterwards, we can undo the additions of those items, and repeat the same process for the range ~[m + 1, r]~. The base case is when ~l = r~, where we can simply retrieve the answer for whatever items are currently in the knapsack (we can treat the queries as a separate event).

Time Complexity: ~\mathcal O(F \cdot \log K \cdot (Q + N) \log(Q + N))~

Alternate Solution

Instead of using divide and conquer, we can group the events from the Euler Tour together in groups of size ~\sqrt{Q + N}~. We will answer the queries in each group together. First, add items to the knapsack that are not modified in the group. For each query, the items that are modified can then be added to the knapsack one by one, and then removed after each query. This method takes slightly longer than the divide and conquer method and may require optimizations to fit within the time limit.

Time Complexity: ~\mathcal O(F \cdot \log K \cdot (Q + N) \sqrt{Q + N})~