Cartesian Tree
Contest: Codeforces Round 616 (Div. 1)
Difficulty rating: 3300
Tags: data structures

Ildar is the algorithm teacher of William and Harris. Today, Ildar is teaching Cartesian Tree. However, Harris is sick, so Ildar is only teaching William.

A cartesian tree is a rooted tree, that can be constructed from a sequence of distinct integers. We build the cartesian tree as follows:

1. If the sequence is empty, return an empty tree;
2. Let the position of the maximum element be $$$x$$$;
3. Remove element on the position $$$x$$$ from the sequence and break it into the left part and the right part (which might be empty) (not actually removing it, just taking it away temporarily);
4. Build cartesian tree for each part;
5. Create a new vertex for the element, that was on the position $$$x$$$ which will serve as the root of the new tree. Then, for the root of the left part and right part, if exists, will become the children for this vertex;
6. Return the tree we have gotten.

For example, this is the cartesian tree for the sequence $$$4, 2, 7, 3, 5, 6, 1$$$:

After teaching what the cartesian tree is, Ildar has assigned homework. He starts with an empty sequence $$$a$$$.

In the $$$i$$$-th round, he inserts an element with value $$$i$$$ somewhere in $$$a$$$. Then, he asks a question: what is the sum of the sizes of the subtrees for every node in the cartesian tree for the current sequence $$$a$$$?

Node $$$v$$$ is in the node $$$u$$$ subtree if and only if $$$v = u$$$ or $$$v$$$ is in the subtree of one of the vertex $$$u$$$ children. The size of the subtree of node $$$u$$$ is the number of nodes $$$v$$$ such that $$$v$$$ is in the subtree of $$$u$$$.

Ildar will do $$$n$$$ rounds in total. The homework is the sequence of answers to the $$$n$$$ questions.

The next day, Ildar told Harris that he has to complete the homework as well. Harris obtained the final state of the sequence $$$a$$$ from William. However, he has no idea how to find the answers to the $$$n$$$ questions. Help Harris!

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 150000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$). It is guarenteed that each integer from $$$1$$$ to $$$n$$$ appears in the sequence exactly once.

Output format:
Print $$$n$$$ lines, $$$i$$$-th line should contain a single integer  — the answer to the $$$i$$$-th question.

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

Note:
After the first round, the sequence is $$$1$$$. The tree is

The answer is $$$1$$$.

After the second round, the sequence is $$$2, 1$$$. The tree is

The answer is $$$2+1=3$$$.

After the third round, the sequence is $$$2, 1, 3$$$. The tree is

The answer is $$$2+1+3=6$$$.

After the fourth round, the sequence is $$$2, 4, 1, 3$$$. The tree is

The answer is $$$1+4+1+2=8$$$.

After the fifth round, the sequence is $$$2, 4, 1, 5, 3$$$. The tree is

The answer is $$$1+3+1+5+1=11$$$.

Example input:
5
2 4 1 5 3

Example output:
1
3
6
8
11

Example input:
6
1 2 4 5 6 3

Example output:
1
3
6
8
12
17

Editorial:
Instead of inserting numbers one by one, let's imagine I have $$$n$$$ blanks in a row, and I will fill the blanks with integers from $$$[1,n]$$$ in order, and I want to know about the cartesian tree after each blank filled.
In the following parts of the solution, I will use positions in the original array instead of positions in the contracted array to label things.
In the process of building a cartesian tree, a node is created for each recursive call of building a tree for a subarray $$$[l,r]$$$. Let's label the node created at that moment to be $$$(l,r)$$$. We realize that $$$r-l+1$$$ will be the size of the subtree of that node. However, in our problem, some positions can be blanks, so the actual subtree size of a node $$$(l,r)$$$ is the number of positions that are not blanks in the subarray $$$[l,r]$$$.
So now we are finding the sum of the number of non-blanks in the range for each node $$$(l,r)$$$ in our cartesian tree. Let $$$pf(r)$$$ be the number of non-blanks in the first $$$r$$$ positions of the sequence. Then we are finding sum of $$$pf(r)-pf(l-1)$$$ for each node $$$(l,r)$$$.
To proceed, observe a property for a cartesian tree. Let's define for each integer $$$p$$$, let $$$maxr(p)$$$ to be the largest $$$r$$$ such that $$$(p,r)$$$ is a node, or just null if there is no nodes of the form $$$(p,r)$$$. Similarly, define $$$minl(p)$$$ to be the smallest $$$l$$$ such that $$$(l,p)$$$ is a node.
Then, for each node $$$(l,r)$$$, exactly one of the following is true:
1. $$$maxr(l)=r$$$.
2. $$$minl(r)=l$$$.
Except when $$$(l,r)$$$ is the root.
If we know:
1. sum of $$$pf(maxr(l))$$$ over all $$$maxr(l)$$$ that is not null.
2. sum of $$$pf(l-1)$$$ over all $$$maxr(l)$$$ that is not null.
3. sum of $$$pf(r)$$$ over all $$$minl(r)$$$that is not null.
4. sum of $$$pf(minl(r)-1)$$$ over all $$$minl(r)$$$ that is not null.
Then we can find out the answer. As it is more or less symmetric I will only care about part (1) and (2) from now on.
Let's find out what would happen to nodes of our tree if we fill $$$i+1$$$ into position $$$x$$$, replacing a blank. Let's omit how the nodes connect each other and just track the labels of each node. For convenience, we will make the following definitions.
• Call $$$prv$$$ the nearest non-blank position on the left side of $$$x$$$.
• Call $$$nxt$$$ the nearest non-blank position on the right side of $$$x$$$.
• Call $$$head$$$ the leftmost non-blank position.
• Call $$$tail$$$ the rightmost non-blank position.
Firstly, every node that is of the form $$$(p,q)$$$ where $$$p \le x \le q$$$, will be split into two halves of $$$(p,prv)$$$ and $$$(nxt,q)$$$. Then, duplicates (nodes that represent the same range) will be removed. Finally, there will be a new node that would represent the root, which is $$$(head,tail)$$$.
Let's track how $$$maxr$$$ changes.
• $$$maxr(p)=\min(maxr(p),prv)$$$ for all p in the range $$$[head,prv]$$$.
• Some modification to values of $$$maxr(head)$$$, $$$maxr(x)$$$ and $$$maxr(nxt)$$$.
As the first step doesn't change whether values are null or not, and modifications to the second step can be easily handled, part (2) can be easily maintained by a Fenwick tree. So it remains to compute part (1).
Imagine instead of computing sum of $$$pf(maxr(l))$$$, we are computing sum of $$$maxr(l)$$$ Then, we realise that we are having a Segment Tree Beats problem. You have to maintain a sequence with 3 kinds of operation:
1. Do $$$a[x]=\min(a[x],v)$$$ for $$$x$$$ in $$$[l,r]$$$.
2. $$$a[x]=v$$$.
3. Query the sum of the whole array.
Check part 2 of this blog and this proof of time complexity.
Then we can solve this variation of the problem in $$$O(n\log n)$$$.
So, we have to modify the above variant into solving the real problem. Look at what we do every time we are doing query 1. We are doing a total of $$$O(n\log n)$$$ times of changing some occurrences of value $$$u$$$ to value $$$v$$$. Which means, we can maintain the frequency for values of $$$maxr$$$. Therefore, for each put-tag operation in our segment tree beats, we just modify a Fenwick tree that represents the frequency of values in $$$maxr$$$. Because we have $$$O(n\log n)$$$ updates to the segment tree, the total time complexity is $$$O(n\log^2 n)$$$.
It is also possible to replace "segment tree beats" with "treap beats" and we can support online queries, but it is not required to pass this problem.
We also allowed methods of slower complexity (i.e. $$$O(n \sqrt{n})$$$) to pass. It basically is the same but does the above things by sqrt decomposition instead. Care is needed to be sure that there is no extra $$$log$$$ factor.