Input for query (a) is O(n), so does it really matter to achieve logarithmic time?

You can try to keep D s.t. A[i] = B[i] * t + D[i] at all times for all i, where t is the number of operations of type a) so far. Then an operation of type b does for each i:

let delta = C — B[i] where B[i] is the old value of B at i; then D[i] -= delta * t

This seems difficult at first but a good observation is that you can rewrite operations of type b) as operations of type B[i] += delta. How so? It's kind of segtree beats, but much more specific: you can consider the potential of B as the number of adjacent positions of different values. When you have an update, you split it in maximal subarrays of equal value and perform operations of B[i] += delta on [x, y]. You'll have an amortized overall of N+M such operations. But they add a constant value to B, so you can make use of that to subtract a constant delta * t from A. You can clearly do this by a segment tree with lazy update (and via a segtree-like implementation, you can divide the range [x, y] into ranges of equal values; alternatively you can keep a set of the pairs where B[i] != B[i+1]). This is a very particular solution. I would be interested in hearing more general or simpler ideas

• the initial values of $$$A$$$ are irrelevant and those of $$$B$$$ can be set by operations of type (b)
• remember which constant subarrays generated by updates exist in $$$B$$$
• in each update, this increases by at most $$$2$$$, so there are $$$O(updates)$$$ "add/remove constant subarray" operations
• for each of these subarrays, we can find how many times it's added to $$$A$$$
• if a subarray with value $$$C$$$ appeared immediately after the $$$k$$$-th operation of type (a) and we've had $$$l$$$ such operations, then $$$C(l-k)$$$ is added once to each element of $$$A$$$ from the corresponding range
• this can be split into a constant part (sum of $$$-Ck$$$) and a linear part (sum of $$$C$$$); each can be handled by a segment tree