Points
Contest: Educational Codeforces Round 131 (Rated for Div. 2)
Difficulty rating: 2500
Tags: combinatorics, data structures, implementation, math, matrices

A triple of points $$$i$$$, $$$j$$$ and $$$k$$$ on a coordinate line is called beautiful if $$$i < j < k$$$ and $$$k - i \le d$$$.

You are given a set of points on a coordinate line, initially empty. You have to process queries of three types:

- add a point;
- remove a point;
- calculate the number of beautiful triples consisting of points belonging to the set.

Input format:
The first line contains two integers $$$q$$$ and $$$d$$$ ($$$1 \le q, d \le 2 \cdot 10^5$$$) — the number of queries and the parameter for defining if a triple is beautiful, respectively.

The second line contains $$$q$$$ integers $$$a_1, a_2, \dots, a_q$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) denoting the queries. The integer $$$a_i$$$ denotes the $$$i$$$-th query in the following way:

- if the point $$$a_i$$$ belongs to the set, remove it; otherwise, add it;
- after adding or removing the point, print the number of beautiful triples.

Output format:
For each query, print one integer — the number of beautiful triples after processing the respective query.

Constraints:
Time limit: 6.5 s
Memory limit: 512.0 MB

Example input:
7 5
8 5 3 2 1 5 6

Example output:
0
0
1
2
5
1
5

Editorial:
We are going to calculate the answer as follows: for every point $$$i$$$, let $$$f(i)$$$ be the number of points $$$j$$$ such that $$$1 \le j - i \le d$$$ (i. e. the number of points that are to the right of $$$i$$$ and have distance at most $$$d$$$ from it). Then, the number of beautiful triples where $$$i$$$ is the leftmost point is $$$\dfrac{f(i)(f(i) - 1)}{2}$$$. We can sum these values over all points to get the answer; so, the solution should somehow maintain and update the sum of these values efficiently.
Let's see what happens when we add a new point or remove an existing point. For all points to the left of it with distance no more than $$$d$$$, the value of $$$f(i)$$$ increases or decreases by $$$1$$$. So, we need some sort of data structure that allows adding/subtracting $$$1$$$ on segment and maintains the sum of $$$\dfrac{f(i)(f(i) - 1)}{2}$$$. This looks like a lazy segment tree, but updating the sum of $$$\dfrac{f(i)(f(i) - 1)}{2}$$$ can be tricky.
One way to do this is to notice that $$$\dfrac{f(i)(f(i) - 1)}{2} = \dfrac{f(i)^2}{2} - \dfrac{f(i)}{2}$$$. So maybe we can maintain the sum of $$$f(i)^2$$$ and the sum of $$$f(i)$$$ on the segment? It turns out we can.
The model solution does this as follows: the leaf of the segment tree corresponding to the position $$$i$$$ stores a vector with three values: $$$(f(i)^0, f(i)^1, f(i)^2)$$$. The inner nodes store the sums of these vectors in the subtree. We can find a matrix which, when multiplied by $$$(x^0, x^1, x^2)$$$, gets the vector $$$((x+1)^0, (x+1)^1, (x+1)^2)$$$, and the inverse matrix to it. Then adding $$$1$$$ to $$$f(i)$$$ on segment means multiplying all vectors on segment by that matrix, and subtracting $$$1$$$ means multiplying by the inverse matrix; and since matrix multiplication is both associative and distributive, the segment tree can handle these queries.
Side note: this method with matrices is asymptotically fine, but the constant factor in it is fairly large. You can speed this up by getting rid of the matrices and instead storing the sum of $$$f(i)$$$ and the sum of $$$f(i)^2$$$ in each node, and coding the formulas that allow you to add/subtract $$$1$$$ on segment by hand, without any matrix operations. This can make a noticeable improvement in terms of actual time consumption, although it wasn't needed in this problem since the time limit was pretty generous.
Okay, there's only one small issue left: right now our structure can store the sum of $$$f(i)$$$ and $$$f(i)^2$$$ over all possible points (we build it on segment $$$[0, 200000]$$$, for example), but we only need the sum over existing points. One way to handle it is to use a flag for each leaf of the segment tree, and pull the value up from the leaf only if this flag is true. We will need a function that changes the value of this flag for a single leaf, but it's not very different from a function that changes one value in a lazy segment tree.
Time complexity of the solution is $$$O(A + q \log A)$$$, where $$$A$$$ is the maximum coordinate of the point, although the constant factor of the described approach is fairly large since it involves $$$3 \times 3$$$ matrix multiplications. You can improve the constant factor by getting rid of the matrices, as mentioned earlier.