One major step in solving this problem is the reduction to solving it for a line of pastures (starting with pasture ~1~) rather than a cycle, which is much more manageable. Let's consider having two lines of ~N~ pastures each. The first line will consist of pastures ~1, 2, \dots, N-1, N~ (made by removing bridge ~N~), while the second will consist of pastures ~1, N, \dots, 3, 2~ (made by removing bridge ~1~). If we compute the number of bananas delivered in each line and add these two values together, it may exceed the number of bananas delivered in the original cycle – but by how much? The only bananas which will be counted twice will be all of those delivered by trucks which are light enough to drive around the entire cycle in either direction – namely, the trucks whose weights are no larger than the minimum weight ~S_i~ supported by any bridge ~i~. Therefore, if we can maintain this minimum value (which is easy) and be able to query the sum of the ~B~ values of trucks whose ~W~ values are no larger than it (which will be doable), we can go ahead and solve the problem for both of these lines independently, and then combine their answers!

Now that we're dealing with a line (let's say the first line, consisting of pastures ~1~ to ~N~ in order), let ~P[i]~ be the maximum truck weight that would be capable of reaching each pasture ~i~. We have ~P[1] = \infty~, while ~P[i] = \min(P[i-1], S[i-1])~ for ~2 \le i \le N~. Note that ~P[1 \dots N]~ is a non-increasing sequence. The number of bananas delivered to pasture ~i~ is then the sum of the ~B~ values of trucks whose ~W~ values are no larger than ~P[i]~. Handling each day independently, we can compute the ~P~ array in ~\mathcal O(N)~ time, and then compute the total number of bananas delivered on it efficiently in various ways. For example, we can consider each truck ~i~ in turn, use binary search to find the last pasture ~j~ that truck ~i~ can reach (i.e., the largest ~j~ such that ~P[j] \ge W[i]~), and add ~B[i] \times (j-1)~ to our result. After computing the results for both lines, we must remember to subtract the double-counted bananas, which can be done by summing the bananas delivered by light-enough trucks in ~\mathcal O(M)~ time. This yields a solution with a running time of ~\mathcal O(D(N+M \log N))~. Similar ~\mathcal O(D(M+N \log M))~ and ~\mathcal O(D(N+M))~ solutions are possible.

In order to optimize this approach, we'll need to be able to update the answer from day to day without re-computing it from scratch, which will require a couple of data structures to maintain and update useful information about the trucks and pastures.

Firstly, for the trucks, it seems useful to be able to query the sum of the ~B~ values of trucks whose ~W~ values are no larger than some given value (for example, this is exactly what's required to compute the number of double-counted bananas each day). Fortunately, there exists a simple data structure which does exactly that – a binary indexed tree (also known as a Fenwick tree). We'll initialize the tree with each truck ~i~ by adding ~B[i]~ to index ~W[i]~, and each time a truck ~i~'s weight changes from ~w~ to ~w'~, we'll subtract ~B[i]~ from index ~w~ and add ~B[i]~ to index ~w'~. We'll be querying this tree for the sum of the ~B~ values of trucks whose ~W~ values are no larger than some weight ~x~ – let's call this sum ~F(x)~. Each update and query on this tree will take ~\mathcal O(\log L)~ time, where ~L~ is the maximum possible truck weight (~10^6~).

Secondly, for the pastures in a line, we'll want a data structure to represent their corresponding ~P~ array. Let's consider only the set of ~K~ "interesting" indices ~P'~ at which ~P~ changes (decreases), plus a sentinel value of ~P'[K] = N+1~. We then have an increasing list ~P'[1 \dots K]~ such that each interval of indices ~P'[i] \dots (P'[i+1]-1)~ has a uniform ~P~ value, which means that each pasture in that interval will receive the same number of bananas (namely, ~F(P[P'[i]])~ of them). To allow this list to be updated as necessary, we'll want to store it as a set (a balanced binary search tree) of pairs ~(i, P[i])~, rather than maintaining the actual arrays ~P~ and ~P'~. This set is initialized in ~\mathcal O(N \log N)~ by iterating over the pastures in order and inserting each one which is preceded by a bridge with a new minimum weight limit. Each time a bridge ~i~'s weight limit is reduced to ~w~, this set can be updated in amortized ~\mathcal O(\log N)~ by potentially adding a point ~(i, w)~, and deleting existing points ~(j, w')~ where ~j \ge i~ and ~w' \ge w~.

Now that both of these data structures are in place, let's consider how to use them to update each line's answer after each event. When a truck ~i~'s weight changes from ~w~ to ~w'~, we should determine how many pastures ~c~ are reachable by trucks with weight ~w~ and how many pastures ~c'~ are reachable by trucks with weight ~w'~, and increase the answer by ~B[i] \times (c'-c)~. Each of these values can be looked up in our set in ~\mathcal O(\log^2 N)~ time using binary search, or even in ~\mathcal O(\log N)~ time if we maintain an accompanying set of points searchable by ~P~ value (in other words a set of pairs ~(P[i], i)~ in addition to the set of pairs ~(i, P[i])~). When a bridge's supported weight decreases and we insert and/or delete points from our set, some intervals of pastures with equal ~P~ values (that is, the intervals between adjacent indices in the set) will change, and we can update the answer accordingly. For example, if an interval of ~k~ pastures all have their ~P~ values reduced from ~p~ to ~p'~, we should decrease the answer by ~F(p)-F(p')~. An amortized constant number of pasture intervals will change as a result of each such event, meaning that it can be handled in amortized ~\mathcal O(\log L)~ time. The total time complexity of this algorithm is ~\mathcal O(M \log L + N \log N + D(\log N + \log L))~, where ~L~ is again the maximum possible truck weight.