If x is fixed you can maintain two segment trees. First one is just simple add and get maximum. After each add operation you query for maximum on the whole sequence and until it’s greater than x add +1 on the second tree in corresponding place and add -inf on this place in the first tree. Complexity O((n+q)logn)

I don’t know what to do if d is integer instead of natural. However, I don't think that kobor's complexity is correct. You use a lazy sum segtree with query for max. For question 2 you use a second segtree for sum query. For question 1 you update the lazy segtree. As he said, we need to find the numbers which weren’t bigger than x previously and now are. So while the query for the maximum is >x we search for the leftmost number in the interval that is >x (binary search the maximum length query with the left end == l that returns <=x, (this is O(log^2(n)) and we don’t know how many times we perform it)), then lazy update the index (i) we found with –inf to eliminate it, and update the i th position in the second segtree to 1. In worst case the complexity would be O(n*log^2(n)+q*log(n))

Do you have a problem link?