Basic idea

Let us divide the offices into ~N/K~ blocks such that each block contains ~K~ consecutive offices. If the companies inside a block are organized in a certain data structure (which we will describe later), moving a company in or out can be accomplished by changing a single block, that is, with complexity ~\mathcal O(\text{structure_delete} + \text{structure_insert})~. Mirko's stroll from ~A~ to ~B~ can be solved by manually checking the ending portions of the interval ~[A, B]~ which do not form a complete block (there will be at most ~2(K-1)~ such checks), and solving the remaining blocks, that are completely contained in ~[A, B]~ (there are at most ~N/K~ such blocks), by querying the corresponding structures. The total complexity of a stroll is then ~\mathcal O(2(K-1) + (N/K) \times \text{structure_query})~. In the complexity formulas above, "~\text{structure_}X~" represents the complexity of operation ~X~ on the data structure.

The data structure

Let us begin by calculating the account balance of company ~i~ on day ~t~:

$$\displaystyle S_{i,t} = (t-T_i) Z_i + S_i = t Z_i + (S_i-T_i Z_i)$$

Notice that the function mapping time to balance is linear, so our structure needs to support queries to find the line with the largest ~y~ value for a given ~x~ coordinate (in our case, ~t~).

This can be done by constructing an upper convex hull of the lines and then using ternary search to find the maximum value for a given ~x~.

However, since the ~x~ value (time) in consecutive queries is increasing, the maximum-valued line 'role' will also move from left to right, so it is sufficient to keep a pointer to the currently maximum-valued line and, given a new ~x~, increment it while the next line to the right has a greater value for ~x~.

In order to construct an upper convex hull out of the lines in time ~\mathcal O(K)~, where ~K~ is the number of lines, we need to have the lines sorted by the coefficient multiplying ~x~ (the slope).

Therefore, our structure will keep track of:

1. the sorted array of lines,
2. the upper convex hull formed by those lines,
3. the pointer to the currently maximum-valued line.

Deleting and inserting a line is done by traversing the sorted array, adding the new line and deleting the old one, which can both be done in ~\mathcal O(K)~. After that, we reconstruct the convex hull and reset the pointer to the first line in the hull.

The complexity of a single query cannot be predicted since it depends on the position of the pointer on the hull, but we can be certain that the pointer will be incremented at most ~K~ times (until it reaches the last line) before the next convex hull rebuild, which resets it. Therefore, if ~P_i~ is the number of pointer resets (i.e. insert and delete queries), the total complexity of all queries on block ~i~ is ~\mathcal O(K(P_i+1)) = \mathcal O(K P_i)~.

Total complexity

Each operation of moving a company in (and moving the existing company out) requires changing a single block with complexity ~\mathcal O(K)~, while the total complexity of all queries is the sum of query complexities for all blocks: ~\mathcal O(K P_1 + K P_2 + \dots + K P_{N/K})~. Since the sum of ~P_i~ is at most ~M~, the complexity equals ~\mathcal O(MK)~. The total complexity is then ~\mathcal O(MK + MN/K + MK)~; if we select ~K = \sqrt N~, this equals ~\mathcal O(M \sqrt N)~.