E - Infinite Operations Editorial by evima
◆ Without updating queries
For a sequence \(A = (A_1, \ldots, A_N)\), let us denote \(F(A) = \sum_{i < j} | A_i - A_j|\). We will show that \(\lim_{n\to\infty} f(n) = F(A) / 2\).
Let us call an operation on \((A_i, A_j)\) good when there is no \(k\) such that \(A_i < A_k < A_j\). We can see that the following holds for an operation in general and a good operation.
- An operation gaining \(x\) points decreases \(F(A)\) by at least \(2x\).
- A good operation gaining \(x\) points decreases \(F(A)\) by exactly \(2x\).
We will omit the proofs since they are easy.
From the definition, \(F(A)\) will never be less than \(0\). Thus, we can first see that \(2f(n) \leq F(A)\) holds for any \(n\).
To show that \(\lim_{n\to\infty} f(n) = F(A) / 2\), it is enough to show that we can make \(F(A)\) tend to \(0\) by repeating good operations only.
We assume \(A_1\leq A_2\leq\cdots\), after reindexing the elements if necessary. Here, a simple calculation shows that \(\forall i, |A_i - A_{i+1}| < C \implies F(A) < \frac{N(N-1)}{2}C\). From its contraposition, we can see that there exists \(i\) such that \(|A_i - A_{i+1}| \geq \frac{2F(A)}{N(N-1)}\). Specifically, it is possible to do a good operation with \(x = \frac{F(A)}{N(N-1)}\), which multiplies \(F(A)\) by exactly \(r = 1 - \frac{2}{N(N-1)}\).
By repeating this \(n\) times, we can make \(F(A)\) multiplied by \(r^n\) in \(n\) good operations. Since \(0\leq r < 1\), this shows that it is possible to make \(F(A)\) tend to \(0\) with good operations only.
◆ Computing the answer and dealing with queries
The order of elements in \(A\) is irrelevant to the problem, so we see \(A\) as a multiset.
Consider computing the increment of the answer while handling additions and deletions of elements. We can see that we just need to compute \(\sum_{a\in A} |x - a|\) for some number \(x\).
This can be computed by retrieving the count and sum of \(a\in A\) in segments \([0, x)\) and \([x, \infty)\). We can do this by compressing the values and using Fenwick Tree or Segment Tree, for example.
It is also possible to directly compute the answer, rather than its increment, with Segment Tree.
◆ Sample Implementations
posted:
last update: