Count Equal-Difference Triples After Each Add or Remove-All Operation

Process a stream of operations on a multiset of integers and, after every operation, report how many triples of elements form an arithmetic progression with common difference `diff`. Each operation is a string. `"+x"` adds one occurrence of the integer `x` to the multiset, and `"-x"` removes every occurrence of `x` from it. After each operation, count the triples `(a, b, c)` of elements currently in the multiset such that `a - b == diff` and `b - c == diff`. ### Function Signature `count_triples_after_each(operations: list[str], diff: int) -> list[int]` ### Rules - The multiset starts empty. - `"+x"` adds one more occurrence of `x`, even if `x` is already present. - `"-x"` removes all occurrences of `x`. If `x` is absent, the operation changes nothing, but a count is still reported for it. - Triples are counted over individual occurrences: a triple chooses one occurrence of a value `a`, one occurrence of `b = a - diff`, and one occurrence of `c = a - 2 * diff`. If those three values occur `p`, `q`, and `r` times, they contribute `p * q * r` triples. - Return one count per operation, in operation order. ### Constraints - `1 <= len(operations) <= 100000`. - Each operation is `+` or `-` followed immediately by the decimal digits of `x`, where `0 <= x <= 1000000000` and there are no leading zeros except for `x = 0` itself. - `1 <= diff <= 1000000000`. Requiring a positive `diff` is a convention of this exercise. - A count can exceed `2^31 - 1` (for example, when three consecutive progression values each occur tens of thousands of times), so use 64-bit arithmetic. Every count stays within `2^53`. ### Examples Input: `operations = ["+4","+5","+6","+4","+3","-4"], diff = 1` Output: `[0,0,1,2,4,0]` After `"+6"`, the values 6, 5, 4 form one triple. The second `"+4"` doubles that to 2. After `"+3"`, the progressions 6, 5, 4 and 5, 4, 3 each contribute 2 triples because 4 occurs twice, giving 4. Removing every 4 leaves no progression. Input: `operations = ["+1","+3","+5","+3","-7","+5"], diff = 2` Output: `[0,0,1,2,2,4]` `"-7"` removes nothing, so the count stays 2. The final `"+5"` makes the occurrence counts of 5, 3, and 1 equal to 2, 2, and 1, giving 4.