Cursor Distance
Contest: Codeforces Round 596 (Div. 1, based on Technocup 2020 Elimination Round 2)
Difficulty rating: 3500

There is a string $$$s$$$ of lowercase English letters. A cursor is positioned on one of the characters. The cursor can be moved with the following operation: choose a letter $$$c$$$ and a direction (left or right). The cursor is then moved to the closest occurence of $$$c$$$ in the chosen direction. If there is no letter $$$c$$$ in that direction, the cursor stays in place. For example, if $$$s = \mathtt{abaab}$$$ with the cursor on the second character ($$$\mathtt{a[b]aab}$$$), then:

- moving to the closest letter $$$\mathtt{a}$$$ to the left places the cursor on the first character ($$$\mathtt{[a]baab}$$$);
- moving to the closest letter $$$\mathtt{a}$$$ to the right places the cursor the third character ($$$\mathtt{ab[a]ab}$$$);
- moving to the closest letter $$$\mathtt{b}$$$ to the right places the cursor on the fifth character ($$$\mathtt{abaa[b]}$$$);
- any other operation leaves the cursor in place.

Let $$$\mathrm{dist}(i, j)$$$ be the smallest number of operations needed to move the cursor from the $$$i$$$-th character to the $$$j$$$-th character. Compute $$$\displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j)$$$.

Input format:
The only line contains a non-empty string $$$s$$$ of at most $$$10^5$$$ lowercase English letters.

Output format:
Print a single integer $$$\displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j)$$$.

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

Note:
In the first sample case, $$$\mathrm{dist}(i, j) = 0$$$ for any pair $$$i = j$$$, and $$$1$$$ for all other pairs.

Example input:
abcde

Example output:
20

Example input:
abacaba

Example output:
58

Editorial:
Again, it's easier to solve the problem backwards. For a character $$$s_i$$$, from which characters $$$s_j$$$ can we reach $$$s_i$$$ in one step? Clearly, $$$s_j$$$ should lie in a subsegment of $$$s$$$ bounded by adjacent occurences of $$$s_i$$$ (inclusive), or by the borders of $$$s$$$. Let's denote this subsegment for $$$s_i$$$ by $$$[L_i, R_i)$$$ (we will use half-open intervals for convenience, as should you).
Which characters can be reached from $$$s_i$$$ in $$$k$$$ reverse steps? We can see that these characters also form a subsegment, let's denote it $$$[L_i^{(k)}, R_i^{(k)})$$$. We have that $$$[L_i^{(0)}, R_i^{(0)}) = [i, i + 1)$$$, and $$$[L_i^{(k)}, R_i^{(k)}) = \displaystyle \cup_{j \in [L_i^{(k - 1)}, R_i^{(k - 1)})} [L_j, R_j)$$$.
Note that having values of $$$[L_i^{(k)}, R_i^{(k)})$$$ can be used to directly compute the answer, for example, with a formula $$$\sum_{i = 1}^n \sum_{k = 0}^{n - 1} (n - (R_i^{(k)} - L_i^{(k)}))$$$. This formula is correct since the expression inside the brackets is the number of characters not reachable from $$$i$$$ in $$$k$$$ reverse steps, hence a position $$$j$$$ reachable in exactly $$$d$$$ steps will be accounted for $$$d$$$ times. Simplifying a bit, we arrive at the formula $$$n^3 - \sum_{i = 1}^n \sum_{k = 0}^{n - 1} (R_i^{(k)} - L_i^{(k)})$$$.
Values of $$$[L_i^{(k)}, R_i^{(k)})$$$ can be computed in $$$O(n^2)$$$ individually by applying the above recurrence and using a sparse table, but that is still way too slow. It's tempting to try and use binary lifting, but as $$$k$$$ grows, evolution of $$$L_i^{(k)}$$$ and $$$R_i^{(k)}$$$ is mutually dependent, and we can't store an $$$n^2$$$-sized table. They do, however, become independent at some point, namely, when the range $$$[L_i^{(k)}, R_i^{(k)})$$$ contains all distinct letters present in $$$s$$$. Indeed, to compute $$$R_i^{(k + 1)}$$$ we simply need to take the largest $$$R_j$$$, where $$$j$$$ ranges over the last occurences of letters a, $$$\ldots$$$, z before $$$R_i^{(k)}$$$. Slightly more generally, we can treat the evolution of $$$L_i^{(k)}$$$ and $$$R_i^{(k)}$$$ independently in a range of $$$k$$$'s where the number of distinct characters in the segment doesn't change. And it can only change at most $$$\alpha = 26$$$ times...
Time to put this together. For each $$$i$$$, we will store $$$k_i$$$ — the number of expansions we've applied to $$$[L_i^{(k)}, R_i^{(k)})$$$, as well as the range's endpoints themselves. We will iterate over the parameter $$$t$$$ — the number of distinct characters in ranges we're going to expand now. For each right endpoint $$$r$$$, let's find $$$f_r(r)$$$ as the largest $$$R_j$$$ over $$$t$$$ closest distinct letters to the left of $$$r$$$; define $$$f_l(l)$$$ similarly. Additionally, compute binary lifts $$$f^{2^y}_r(r)$$$, $$$f^{2^y}_l(l)$$$, as well as the sums of $$$r$$$ and $$$l$$$ visited by each binary lift. Now, for each $$$i$$$ we use binary lifting to find the largest number of iterations to apply to $$$[L_i^{(k)}, R_i^{(k)})$$$ so that the number of distinct characters in the range stays equal to $$$t$$$. Doing this, we can update $$$k_i$$$ and endpoints of $$$[L_i^{(k)}, R_i^{(k)})$$$ accordingly, as well as add a part of $$$\sum_{i = 1}^n \sum_{k = 0}^{n - 1} (R_i^{(k)} - L_i^{(k)})$$$ to the total. Thus, going into the next phase with $$$t + 1$$$, we will have all necessary values up-to-date.
How fast does this work? For every $$$t = 1, \ldots, \alpha = 26$$$, we'll need $$$O(n \log n)$$$ work to construct binary lifts and update everything. The total complexity is thus $$$O(\alpha n \log n)$$$.