一、题目重述

给定一棵 $n$ 个节点的有根树的括号序列表示（长度为 $2(n-1)$），初始序列已知。
然后进行 $q$ 次操作，每次交换序列中两个不同位置的字符（保证交换后仍为合法括号序列）。
每次操作后，需要输出当前树的直径（最长简单路径的长度）。

数据范围：$n, q \le 10^5$。

---

二、括号序列与树的对应关系

对于一个 $n$ 个节点的有根树，其括号序列长度为 $2(n-1)$，由以下方式生成：

• 从根出发，进行 DFS，每进入一个子节点时记录 (，每返回时记录 )。

性质：

• 序列中 ( 和 ) 的数量相等，各为 $n-1$。
• 任意前缀中 ( 的数量 $\ge$ ) 的数量。
• 每个节点对应一个匹配的括号对。
• 节点的深度 = 该节点对应的 ( 的嵌套深度。

---

三、直径与括号序列的关系

设 $d_i$ 为括号序列中第 $i$ 个位置的深度（即从根到该位置的括号嵌套层数）。
则树中任意两个节点 $u, v$ 的距离为：

$$\text{dist}(u, v) = d_u + d_v - 2 \cdot d_{\text{lca}(u, v)} $$

其中 $\text{lca}(u, v)$ 的深度等于 $u$ 和 $v$ 之间所有位置的最小深度（因为括号序列中，LCA 对应的是 $u$ 和 $v$ 的括号对之间深度最小的点）。

因此，树的直径为：

$$\text{diameter} = \max_{1 \le l \le r \le 2(n-1)} \left( d_l + d_r - 2 \cdot \min_{k \in [l, r]} d_k \right) $$

---

四、经典转化

定义 $f(i) = d_i$。则：

$$\text{diameter} = \max_{l \le m \le r} \left( f(l) + f(r) - 2f(m) \right) $$

其中 $m$ 是区间 $[l, r]$ 内 $f$ 的最小值点。

我们可以用线段树维护以下信息来快速计算这个最大值：

名称	含义	公式
$\text{maxL}$	区间内 $\max f(l)$	$\max(f(l))$
$\text{maxR}$	区间内 $\max f(r)$	$\max(f(r))$
$\text{maxM}$	区间内 $\max (-2f(m))$	$\max(-2f(m))$
$\text{maxLM}$	区间内 $\max (f(l) - 2f(m))$	$\max(f(l) - 2f(m))$
$\text{maxMR}$	区间内 $\max (-2f(m) + f(r))$	$\max(-2f(m) + f(r))$
$\text{maxLR}$	区间内 $\max (f(l) - 2f(m) + f(r))$	即直径

---

五、线段树合并

对于两个子区间 $L$ 和 $R$，合并后区间 $M$ 的信息为：

$$\begin{aligned} \text{maxL}_M &= \max(\text{maxL}_L, \text{maxL}_R) \\ \text{maxR}_M &= \max(\text{maxR}_L, \text{maxR}_R) \\ \text{maxM}_M &= \max(\text{maxM}_L, \text{maxM}_R) \\ \text{maxLM}_M &= \max(\text{maxLM}_L, \text{maxLM}_R, \text{maxL}_L + \text{maxM}_R) \\ \text{maxMR}_M &= \max(\text{maxMR}_L, \text{maxMR}_R, \text{maxM}_L + \text{maxR}_R) \\ \text{maxLR}_M &= \max(\text{maxLR}_L, \text{maxLR}_R, \text{maxL}_L + \text{maxMR}_R, \text{maxLM}_L + \text{maxR}_R) \end{aligned} $$

这些合并公式保证了 $O(1)$ 的合并时间。

---

六、处理交换操作

交换两个位置 $l$ 和 $r$ 的括号（$l < r$），只会影响区间 $[l, r-1]$ 的深度值：

• 如果 $s[l] = '('$ 且 $s[r] = ')'$，则区间 $[l, r-1]$ 的深度全部 $-2$（因为一个 ( 向右移动，中间的括号嵌套层数减少）
• 如果 $s[l] = ')'$ 且 $s[r] = '('$，则区间 $[l, r-1]$ 的深度全部 $+2$
• 如果 $s[l] = s[r]$，深度不变

因此，每次交换只需要对线段树进行一次区间加操作（$O(\log n)$），然后根节点的 maxLR 就是当前树的直径。

---

七、算法步骤

1. 读入 $n, q$ 和初始括号序列 $s$。
2. 计算每个位置的深度 $d_i$。
3. 建立线段树，叶子节点存储 $f(i) = d_i$。
4. 输出初始直径 = maxLR[1]。
5. 对于每次操作：
   • 读入 $l, r$，保证 $l \le r$。
   • 如果 $s[l-1] \neq s[r-1]$：
     • 若 $s[l-1] = '('$，则对区间 $[l, r-1]$ 加 $-2$
     • 否则对区间 $[l, r-1]$ 加 $+2$
     • 交换 $s[l-1]$ 和 $s[r-1]$
   • 输出当前直径 = maxLR[1]

---

八、复杂度分析

• 建树：$O(n)$
• 每次操作：$O(\log n)$ 区间加 + $O(1)$ 查询
• 总复杂度：$O((n + q) \log n)$，可过 $n, q \le 10^5$

---

九、最终代码（标程）

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
const int INF = 1e9;

int n, q;
string s;
int depth[N];

struct Node {
    int maxL, maxR, maxM, maxLM, maxMR, maxLR;
    int lazy;
} tr[N << 2];

void push_up(int u) {
    int l = u << 1, r = u << 1 | 1;
    tr[u].maxL = max(tr[l].maxL, tr[r].maxL);
    tr[u].maxR = max(tr[l].maxR, tr[r].maxR);
    tr[u].maxM = max(tr[l].maxM, tr[r].maxM);
    tr[u].maxLM = max({tr[l].maxLM, tr[r].maxLM, tr[l].maxL + tr[r].maxM});
    tr[u].maxMR = max({tr[l].maxMR, tr[r].maxMR, tr[l].maxM + tr[r].maxR});
    tr[u].maxLR = max({tr[l].maxLR, tr[r].maxLR, tr[l].maxL + tr[r].maxMR, tr[l].maxLM + tr[r].maxR});
}

void apply(int u, int add) {
    tr[u].maxL += add;
    tr[u].maxR += add;
    tr[u].maxM -= 2 * add;
    tr[u].maxLM -= add;
    tr[u].maxMR -= add;
    tr[u].lazy += add;
}

void push_down(int u) {
    if (tr[u].lazy) {
        apply(u << 1, tr[u].lazy);
        apply(u << 1 | 1, tr[u].lazy);
        tr[u].lazy = 0;
    }
}

void build(int u, int l, int r) {
    if (l == r) {
        int d = depth[l];
        tr[u] = {d, d, -2 * d, -d, -d, 0, 0};
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    push_up(u);
}

void update(int u, int l, int r, int ql, int qr, int val) {
    if (ql > r || qr < l) return;
    if (ql <= l && r <= qr) {
        apply(u, val);
        return;
    }
    push_down(u);
    int mid = (l + r) >> 1;
    update(u << 1, l, mid, ql, qr, val);
    update(u << 1 | 1, mid + 1, r, ql, qr, val);
    push_up(u);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> q;
    cin >> s;
    
    int len = 2 * (n - 1);
    int cur = 0;
    for (int i = 0; i < len; ++i) {
        if (s[i] == '(') {
            cur++;
            depth[i + 1] = cur;
        } else {
            depth[i + 1] = cur;
            cur--;
        }
    }
    
    build(1, 1, len);
    
    cout << tr[1].maxLR << '\n';
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        if (l > r) swap(l, r);
        
        if (s[l - 1] != s[r - 1]) {
            if (s[l - 1] == '(') {
                update(1, 1, len, l, r - 1, -2);
            } else {
                update(1, 1, len, l, r - 1, 2);
            }
            swap(s[l - 1], s[r - 1]);
        }
        
        cout << tr[1].maxLR << '\n';
    }
    
    return 0;
}

---

十、正确性总结

• 利用括号序列与树的深度关系，将树的直径转化为括号序列上的一种最大值问题
• 使用线段树维护六个关键值，支持区间加和合并
• 每次交换操作转化为区间加，$O(\log n)$ 更新，$O(1)$ 查询
• 总复杂度 $O((n+q)\log n)$，完美满足数据范围