Alice and the Unfair Game
Contest: Codeforces Round 593 (Div. 2)
Difficulty rating: 2500
Tags: binary search, data structures, dp, dsu

Alice is playing a game with her good friend, Marisa.

There are $$$n$$$ boxes arranged in a line, numbered with integers from $$$1$$$ to $$$n$$$ from left to right. Marisa will hide a doll in one of the boxes. Then Alice will have $$$m$$$ chances to guess where the doll is. If Alice will correctly guess the number of box, where doll is now, she will win the game, otherwise, her friend will win the game.

In order to win, Marisa will use some unfair tricks. After each time Alice guesses a box, she can move the doll to the neighboring box or just keep it at its place. Boxes $$$i$$$ and $$$i + 1$$$ are neighboring for all $$$1 \leq i \leq n - 1$$$. She can also use this trick once before the game starts.

So, the game happens in this order: the game starts, Marisa makes the trick, Alice makes the first guess, Marisa makes the trick, Alice makes the second guess, Marisa makes the trick, $$$\ldots$$$, Alice makes $$$m$$$-th guess, Marisa makes the trick, the game ends.

Alice has come up with a sequence $$$a_1, a_2, \ldots, a_m$$$. In the $$$i$$$-th guess, she will ask if the doll is in the box $$$a_i$$$. She wants to know the number of scenarios $$$(x, y)$$$ (for all $$$1 \leq x, y \leq n$$$), such that Marisa can win the game if she will put the doll at the $$$x$$$-th box at the beginning and at the end of the game, the doll will be at the $$$y$$$-th box. Help her and calculate this number.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$, separated by space ($$$1 \leq n, m \leq 10^5$$$) — the number of boxes and the number of guesses, which Alice will make.

The next line contains $$$m$$$ integers $$$a_1, a_2, \ldots, a_m$$$, separated by spaces ($$$1 \leq a_i \leq n$$$), the number $$$a_i$$$ means the number of the box which Alice will guess in the $$$i$$$-th guess.

Output format:
Print the number of scenarios in a single line, or the number of pairs of boxes $$$(x, y)$$$ ($$$1 \leq x, y \leq n$$$), such that if Marisa will put the doll into the box with number $$$x$$$, she can make tricks in such way, that at the end of the game the doll will be in the box with number $$$y$$$ and she will win the game.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, the possible scenarios are $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$, $$$(3, 3)$$$.

Let's take $$$(2, 2)$$$ as an example. The boxes, in which the doll will be during the game can be $$$2 \to 3 \to 3 \to 3 \to 2$$$

Example input:
3 3
2 2 2

Example output:
7

Example input:
5 2
3 1

Example output:
21

Editorial:
First there is a conclusion: each start point will be able to reach a consecutive segment of end points except for n=1.
It's easy to prove, when a place is banned, we can make a move to make it reachable again.
So with the conclusion then we can solve the problem. First we will come up with a greedy algorithm. We can move the doll to the left (or right) if possible, otherwise we can keep it at its place. Then we will get the left bound and the right bound of one start point. It's $$$O(n^2)$$$ and not enough to pass.
Consider we try to find the left bound. We scan the array $$$a$$$ and deal with all start points together. For the first element of $$$a$$$, it will only influence one start point (that is, if we start from there, we will meet the element can then we need to keep it at its place). So we can move the start point to its right box (because when it starts from that place, we will get the same answer). Then we can delete the first element. But then there will be more than one start point in the same cell, we can use dsu to merge two set of start points.
Note that the doll cannot move to $$$0$$$ or $$$n+1$$$. We can also have to deal with this using the algorithm above. And it is the same to find the right bound.
Time complexity is $$$O(n)$$$.
Another solution: Consider a grid that there is obstacles on $$$(i,a_i)$$$. Each time we start from $$$(0,y)$$$ and if there is no obstacle on $$$(x+1,y-1)$$$ then we move to it, otherwise we move to $$$(x,y-1)$$$. We find we may change the direction only if we reach the place $$$(i-1,a_i+1)$$$ and we will walk to $$$(i,a_i+1)$$$. So only the $$$O(k)$$$ positions are useful. We can use binary search to find the next position for each useful position and start point. Then we get a tree. Just using dfs then we will get left bound for each start points. The Time complexity is $$$O(nlogn)$$$.