题解说明

问题背景：
给定一个排列数组 $p[1..n]$，需要对其划分区间并计算每个位置的某种统计量。代码通过复杂的数据结构（树状数组、链表、并查集）和双向处理技巧，完成对每个区间的答案计算。

核心思路：
$1.$ 区间划分

• 遍历数组 $p$，维护当前最大值 $mx$。
• 当 $mx == i$ 时，说明 $[lst+1, i]$ 是一个完整区间（排列的前缀最大值刚好覆盖到 $i$）。
• 将该区间作为独立子问题处理。

$2.$ 区间标准化

• 将区间 $[l,r]$ 内的值映射为 $1..n$ 的连续整数，存入数组 $a$。
• 初始化答案数组 $ans[i] = n-1$，表示基础贡献。

$3.$ solve 函数（核心）

• 使用树状数组维护前缀和，用于快速统计小于某值的元素个数。
• 使用 $ls[i], rs[i]$ 记录每个位置向左/向右扩展到的最小值位置。
• 每个元素初始为独立集合，集合存储区间 $[X[i], Y[i]]$。
• 从大到小遍历值，逐步合并集合，更新答案。
• 合并时使用链表和并查集思想，保证小集合并入大集合，减少复杂度。

$4.$ 双向处理

• 为了覆盖所有情况，除了正向处理，还需要反向处理：
  • 将 $a[i]$ 映射为 $n-a[i]+1$，再整体反转。
  • 同时反转 $ans$ 数组，保证对应关系。
  • 再次调用 solve，补充计算答案。
• 最终再反转回来，得到完整答案。

$5.$ 输出

• 每个区间处理完毕后，输出该区间的所有 $ans[i]$。

复杂度分析：

• 每个区间内的处理主要依赖树状数组（$O(\log n)$）和集合合并（均摊 $O(n \log n)$）。
• 整体复杂度约 $O(n \log n)$，适合 $n \leq 2 \times 10^5$ 的数据范围。

实现细节：

• 树状数组用于快速统计前缀和。
• $ls/rs$ 数组通过逆序遍历构建，保证能快速找到左右边界。
• 合并集合时维护 $tg$（标记值），避免重复更新，保证效率。
• 双向处理是关键技巧，确保所有情况都被覆盖。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

int len, m;               // len：字符串长度；m：允许的最大删除括号对数（输入m后减1，实际允许m对）
char s[100005];           // 存储输入的括号字符串
int sta[100005], tot;     // 栈：用于匹配括号；tot：栈顶指针
int n, l[100005], r[100005];  // n：有效括号对总数；l/r[i]：第i个括号对的左右端点
vector<int> e[100005];    // 树的邻接表：e[u]存储u的子节点（括号对的包含关系）
const ll M = 1000000;     // 大常数：用于分离“代价”和“删除计数”（避免精度混淆）
ll k;                     // 二分查找的中间值：当前尝试的“删除单个括号对的代价系数”
ll f[100005][2];          // DP数组：f[u][0]不删除u的代价；f[u][1]删除u的代价
int c[100005];            // 临时数组：存储连续子节点集合（用于dp函数处理）
ll sum[100005], g[100005], _g[100005];  // sum：前缀和；g/_g：dp函数的辅助数组

// 向量结构体：用于凸包优化（斜率优化DP），存储(x,y)点
struct Vec {
    ll x, y;
    // 向量减法：返回当前点减b点的向量（用于计算斜率）
    Vec operator -(const Vec &b)const {
        Vec c;
        c.x = b.x - x;
        c.y = b.y - y;
        return c;
    }
    // 比较运算符：按斜率大小排序（用于凸包维护，避免浮点运算）
    // 原理：向量a的斜率 < 向量b的斜率 等价于 a.y*b.x < b.y*a.x
    bool operator <(const Vec &b)const {
        return y * b.x < b.y * x;
    }
} q[100005];  // 凸包队列：存储维护的点，用于斜率优化
int head, tail;  // 凸包队列的头/尾指针

// 子DP函数：处理连续子节点集合，计算合并后的f0/f1（不删/删当前集合的总代价）
void dp(int tot, ll &f0, ll &f1) {
    ll v0 = 1e18, v1 = 1e18;  // v0：不删当前集合的最小代价；v1：删当前集合的最小代价

    // 计算sum数组：sum[i] = 前i个节点的f[c[j]][0]之和（不删子节点的基础代价）
    for (int i = 1; i <= tot; i++)
        sum[i] = sum[i - 1] + f[c[i]][0];

    // 初始化凸包队列：加入初始点(0, 0)
    head = tail = 1;
    q[1] = (Vec) {0, 0};

    // 斜率优化DP：计算g[i]和_g[i]
    for (int i = 1; i <= tot; i++) {
        g[i] = 1e18;  // 初始化当前g[i]为极大值
        // 构造查询向量：用于找到凸包中最优的前驱点（最小化斜率）
        Vec qwq = (Vec) {1, M * i};

        // 弹出队头：若队头两个点的斜率小于查询斜率，队头不是最优，弹出
        while (head < tail && qwq < q[head + 1] - q[head])
            head++;

        // 取最优前驱点p，计算g[i]（当前节点i的代价）
        int p = q[head].x;
        g[i] = _g[p] - M * i * p + f[c[i]][1] + sum[i - 1] + M / 2 * (1ll * i * i - 3 * i) + M;
        // 计算_g[i]：g[i]的变形，用于后续凸包维护（整理成y = kx + b形式）
        _g[i] = g[i] - sum[i] + M / 2 * i * i + M / 2 * 3 * i;

        // 构造当前点，加入凸包队列
        qwq = (Vec) {i, _g[i]};
        // 弹出队尾：若队尾三个点构成的折线不是下凸，弹出队尾（维护凸包性质）
        while (head < tail && qwq - q[tail] < q[tail] - q[tail - 1])
            tail--;
        q[++tail] = (Vec) {i, _g[i]};
    }

    // 反向计算v0和v1：合并后续节点的代价
    ll val = 0;  // val：累加后续节点的f[c[j]][0]（不删子节点的代价）
    for (int j = tot; j >= 0; j--) {
        // 计算不删当前集合的代价：g[j] + 后续代价 + 位置相关代价
        v0 = min(v0, g[j] + val + M * (tot - j) * (tot - j - 1) / 2);
        // 计算删当前集合的代价（j>0时，当前节点存在）
        if (j > 0)
            v1 = min(v1, g[j] + val + M * (tot - j) * (tot - j - 1) / 2);
        // 累加后续节点的不删代价
        if (j > 0)
            val += f[c[j]][0];
    }

    // 更新输入的f0和f1：合并当前集合的代价到总代价
    ll _f0 = f0 + v0, _f1 = min(f1 + v0, f0 + v1);
    f0 = _f0, f1 = _f1;
    return;
}

// 深度优先搜索：遍历括号树，计算每个节点的f[u][0]和f[u][1]
void dfs(int now) {
    // 初始化当前节点的代价：不删/删的初始代价为0
    f[now][0] = f[now][1] = 0;
    int cnt = (int)e[now].size();  // 当前节点的子节点数量
    int t = 0;  // 标记连续子节点的序号（用于计算位置相关代价）

    // 第一步：计算f[now][0]（不删除当前节点的代价）
    for (int i = 0; i < cnt; i++) {
        int v = e[now][i];  // 当前子节点v
        // 判断v是否与前一个子节点连续（前一个子节点的右端点+1 == 当前子节点的左端点）
        if (i == 0 || r[e[now][i - 1]] + 1 != l[e[now][i]])
            t = 1;  // 不连续，重置序号为1
        else
            t++;  // 连续，序号+1
        dfs(v);  // 递归处理子节点v
        // 累加子节点不删的代价 + 连续位置的代价（M*(t-1)）
        f[now][0] += f[v][0] + M * (t - 1);
    }
    // 若当前节点不是根（now!=0，根代表整个括号结构），额外加一个基础代价M
    if (now != 0)
        f[now][0] += M;

    // 第二步：若当前节点是叶子（无子女，即单个括号对），计算f[now][1]（删除当前节点的代价）
    if (cnt == 0) {
        // 删除代价 = M*k（k为当前二分的系数） + 1（标记删除计数，模M后体现）
        f[now][1] = M * k + 1;
        return;
    }

    // 第三步：若当前节点有子女，计算f[now][1]（删除当前节点的代价）
    ll f0 = 0, f1 = 1e18;  // f0：不删当前子集合的代价；f1：删当前子集合的代价（初始极大值）
    for (int i = 0; i < cnt; i++) {
        int j = i;
        // 找到连续的子节点区间：从i到j，子节点的端点连续
        while (j < cnt - 1 && r[e[now][j]] + 1 == l[e[now][j + 1]])
            j++;
        // 将连续区间的子节点存入c数组
        int tot = 0;
        for (int k = i; k <= j; k++)
            c[++tot] = e[now][k];
        // 调用dp函数处理该连续区间，更新f0和f1
        dp(tot, f0, f1);
        i = j;  // 跳过已处理的连续区间
    }
    // 当前节点删除的代价 = 子集合删除的最小代价f1
    f[now][1] = f1;
    return;
}

int main() {
    // 输入字符串长度和允许删除的括号对数（m减1，因为题目输入可能是“最多m对”的偏移）
    cin >> len >> m;
    m--;
    scanf("%s", s + 1);  // 读取括号字符串（1-based索引）

    // 第一步：匹配括号对，记录每个有效括号对的左右端点
    for (int i = 1; i <= len; i++) {
        if (s[i] == '(')
            sta[++tot] = i;  // 左括号入栈，记录位置
        else if (tot > 0) {  // 右括号且栈非空，匹配成功
            ++n;  // 有效括号对计数+1
            l[n] = sta[tot];  // 第n对的左端点 = 栈顶左括号位置
            r[n] = i;         // 第n对的右端点 = 当前右括号位置
            tot--;            // 栈顶出栈
        }
    }

    // 第二步：构建括号树（按包含关系）
    tot = 0;
    sta[0] = 0;  // 栈底为根节点0（代表整个结构）
    // 反向遍历括号对（从最后一对到第一对），确定包含关系
    for (int i = n; i >= 1; i--) {
        // 弹出栈中右端点 > 当前括号对左端点的节点（当前括号对不包含这些节点）
        while (tot > 0 && r[i] < l[sta[tot]])
            tot--;
        // 当前节点i的父节点为栈顶节点，加入邻接表
        e[sta[tot]].push_back(i);
        sta[++tot] = i;  // 当前节点入栈，供后续节点判断包含
    }

    // 第三步：排序每个节点的子节点（按左端点升序，保证处理顺序正确）
    for (int i = 0; i <= n; i++)
        sort(e[i].begin(), e[i].end());

    // 第四步：二分查找最优k值（删除单个括号对的代价系数）
    ll l = 0, r = 1e10, ans = -1;  // 二分范围：0~1e10；ans：最终答案
    while (l <= r) {
        k = (l + r) / 2;  // 当前二分的中间值k
        dfs(0);           // 递归计算根节点的代价
        ll val = min(f[0][0], f[0][1]);  // 根节点的最小总代价（不删/删根的最小值）
        ll cnt = val % M;  // 代价模M：得到删除的括号对数量（因为每次删加1，模M后保留计数）

        // 判断删除数量是否符合要求（<=m）
        if (cnt <= m) {
            // 符合要求：更新答案，尝试更小的k（减少总代价）
            ans = val / M - k * m;  // 总代价//M - k*m：还原真实代价（去除k的影响）
            r = k - 1;
        } else {
            // 不符合要求：需要更大的k（增加删除代价，减少删除数量）
            l = k + 1;
        }
    }

    // 输出最终答案
    cout << ans << endl;
    return 0;
}