Tree Generator™
Contest: Codeforces Round 556 (Div. 1)
Difficulty rating: 2700
Tags: data structures, implementation, trees

Owl Pacino has always been into trees — unweighted rooted trees in particular. He loves determining the diameter of every tree he sees — that is, the maximum length of any simple path in the tree.

Owl Pacino's owl friends decided to present him the Tree Generator™ — a powerful machine creating rooted trees from their descriptions. An $$$n$$$-vertex rooted tree can be described by a bracket sequence of length $$$2(n - 1)$$$ in the following way: find any walk starting and finishing in the root that traverses each edge exactly twice — once down the tree, and later up the tree. Then follow the path and write down "(" (an opening parenthesis) if an edge is followed down the tree, and ")" (a closing parenthesis) otherwise.

The following figure shows sample rooted trees and their descriptions:

Owl wrote down the description of an $$$n$$$-vertex rooted tree. Then, he rewrote the description $$$q$$$ times. However, each time he wrote a new description, he picked two different characters in the description he wrote the last time, swapped them and wrote down the resulting string. He always made sure that each written string was the description of a rooted tree.

Pacino then used Tree Generator™ for each description he wrote down. What is the diameter of each constructed tree?

Input format:
The first line of the input contains two integers $$$n, q$$$ ($$$3 \le n \le 100\,000$$$, $$$1 \le q \le 100\,000$$$) — the number of vertices in the tree and the number of changes to the tree description. The following line contains a description of the initial tree — a string of length $$$2(n-1)$$$ consisting of opening and closing parentheses.

Each of the following $$$q$$$ lines describes a single change to the description and contains two space-separated integers $$$a_i, b_i$$$ ($$$2 \leq a_i, b_i \leq 2n-3$$$) which identify the indices of two brackets to be swapped. You can assume that the description will change after each query, and that after each change a tree can be constructed from the description.

Output format:
Output $$$q + 1$$$ integers — the diameter of each constructed tree, in the order their descriptions have been written down.

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

Note:
The following figure shows each constructed tree and its description in the first example test:

Example input:
5 5
(((())))
4 5
3 4
5 6
3 6
2 5

Example output:
4
3
3
2
4
4

Example input:
6 4
(((())()))
6 7
5 4
6 4
7 4

Example output:
4
4
4
5
3

Editorial:
Take any rooted tree and its description. For any vertices $$$u$$$, $$$v$$$, let $$$h(v)$$$ be its depth in the tree, and $$$d(u, v) = h(u) + h(v) - 2h(\mathrm{lca}(u, v))$$$ be the distance between $$$u$$$ and $$$v$$$.
Consider the traversal of the tree represented by the description. Let's say we're processing the parentheses one by one each second, and let's set $$$\mu(t)$$$ be the current depth after $$$t$$$ seconds. Moreover, let $$$t_u$$$ and $$$t_v$$$ be the moments of time when we're in vertices $$$u, v$$$, respectively (there might be multiple such moments; pick any). Therefore, $$$h(u) = \mu(t_u)$$$ and $$$h(v) = \mu(t_v)$$$.
Assume without the loss of generality that $$$t_u < t_v$$$ and consider the part of the description between the $$$t_u$$$-th and $$$t_v$$$-th second. What is the shallowest vertex we visit during such traversal? As the description represents a depth-first search of the tree, it must be $$$\mathrm{lca}(u, v)$$$. Therefore, $$$h(\mathrm{lca}(u, v)) = \min_{t_l \in [t_u, t_v]} \mu(t_l)$$$. It follows that $$$d(u, v) = \max_{t_l \in [t_u, t_v]} \left(\mu(t_u) + \mu(t_v) - 2\mu(t_l)\right)$$$.
Eventually, the diameter is equal to $$$\max_{u, v} d(u, v) = \max_{t_u \leq t_l \leq t_v} \left(\mu(t_u) - 2\mu(t_l) + \mu(t_v)\right)$$$. This leads to a slow $$$O(n)$$$ solution for computing a single diameter without constructing the tree: consider the parentheses one by one, and maintain the current depth and maximum values of $$$\mu(a)$$$, $$$\mu(a) - 2\mu(b)$$$ and $$$\mu(a) - 2\mu(b) + \mu(c)$$$ for $$$a \leq b \leq c$$$ on the prefix. However, we still need to be able to process the updates quicker than in linear time.
It turns out we can maintain a segment tree. Each node will maintain some information about the substring of the description. Note that such substring doesn't have to describe the whole tree, and so the number of opening and closing parentheses doesn't have to match and it can happen that we're at a negative depth when following the description.
We'll hold the following information about the substring. We assume everywhere that $$$a \leq b \leq c$$$:
• $$$\delta$$$ (the final depth, might be non-zero),
• $$$\max \mu(a)$$$, $$$\max (-2\mu(b))$$$, $$$\max (\mu(a) - 2\mu(b))$$$, $$$\max(-2\mu(b) + \mu(c))$$$, $$$\max (\mu(a) - 2\mu(b) + \mu(c))$$$.
It's now pretty straightforward to combine the informations about two neighboring substrings into a single information about the concatenation of the substrings. Note for example that $$$\delta = \delta_L + \delta_R$$$ and $$$\max \mu(a) = \max\left\{ \max_L \mu(a),\ \max_R \mu(a) + \delta_L\right\}$$$. This allows to maintain the segment tree over the description and process the single character replacement in $$$O(\log n)$$$ time. Therefore, we can process each query in $$$O(\log n)$$$ time, and solve the whole task in $$$O(n + q \log n)$$$ time.
Notably, square-root decomposition isn't much slower in this task; $$$O(\sqrt{n})$$$ per query should pass if you aren't deliberately trying to write as slow code as possible.