Optimizing Efficiency in a Stack
Just be lazy. Don't do what you're told. They'll never know.
Instead of truly increasing the bottom i values right away, just make a note at the i-th value from the bottom to increase it by v when it gets popped. And when that pop happens, move the note to the value below, so it gets increased by v as well (when it gets popped). And so on, so that this will add v to all bottom i values (when they get popped).
To support multiple inc operations: If a value already has a note to add w to it (and all values below it), change that to w + v.
For easier coding, just store all values along with such a note, but with initial adding value 0.
Now all three operations are O(1).
Oh wait. Not quite O(1), since you're using a deque so you can't access an arbitrary index in O(1). That's actually a problem in your solution as well. Your increasing the bottom i values isn't O(i) but only O(i2). If you switch to a list, yours would be O(i) and mine would be O(1). This loses the O(1) of appending/popping to/from a deque, but the list still does them in amortized O(1). So then all three operations are amortized O(1). Alternatively you could keep your deque and store the notes in a separate dict, but then it's O(1) just as much as dict access is O(1) (i.e., not truly, but practically), and I suspect it would be a bit slower than the list version.