2.5 括号匹配

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

YellowStar 某天得到了一个长度为 \(n\) 的括号序列 \(p\)，Yellowstar 现在进行 \(m\) 次询问，每次询问一个区间\([l,r]\)，他想知道子序列\(p_l,p_{l+1},\cdots, p_r\)最大括号匹配数量，请你帮助他。最大括号匹配数量的定义是：这个序列中，最长合法括号子序列的长度。例如“())()”括号序列，他的最长合法括号子序列为“()()”，长度为 4。

数据输入

每组样例第输入的第 1 行包含一个长度为 \(n\ (1\leq n\leq 10^5)\)的括号序列，\(p_1,p_2,\cdots p_n\)。\(p_i\)满足是‘(’或‘)’；接下来一行输入一个 \(m\)，表示询问次数；接下来 \(m\) 行，每行包含两个数字 \(l,r\ (1\leq l\leq r \leq n)\)。

数据输出

对于每次询问，输出一个数字表示答案。

输入示例 输出示例
())(())(())(
7
1 2
1 1
2 3
5 11
1 12
8 12
2 10		 2
0
0
6
10
4
6

数据范围

\(80\%\)的得分点，\(n \leq 1000\)，\(m \leq 1000\)；\(20\%\)的得分点，\(n \leq 100000\)，\(m \leq 100000\)。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define dd(x) cout << #x << " = " << x << ", "
#define de(x) cout << #x << " = " << x << endl
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn = 100005;
char p[maxn];

struct Info {
    int left, right, plen;
    Info() {}
    Info(int _left, int _right, int _plen) {
        left = _left, right = _right, plen = _plen;
    }
    Info operator+(const Info &info) const {
        //当前节点左右括号数量直接由左右子树括号数累加
        //而配对的括号数为分别配对的括号数之和
        //再加上左子树剩余左括号量与右子树剩余右括号量能够配对的数量
        return Info(left + info.left, right + info.right,
            plen + info.plen + min(left - plen, info.right - info.plen));
    }
    void output() {
        dd(left), dd(right), de(plen);
    }
};

struct SegmentTree {
#define ls ((t)<<1)
#define rs ((t)<<1|1)
    Info info[maxn << 2];
    void build(int t, int l, int r) {
        if (l == r) {
            info[t] = Info(p[l] == '(', p[l] == ')', 0);
        }
        else {
            int z = (l + r) >> 1;
            build(ls, l, z), build(rs, z + 1, r);
            info[t] = info[ls] + info[rs];
        }
    }
    Info query(int t, int l, int r, int L, int R) {
        if (L <= l && r <= R) return info[t];
        int z = (l + r) >> 1;
        if (R <= z) return query(ls, l, z, L, R);
        if (L > z) return query(rs, z + 1, r, L, R);
        return query(ls, l, z, L, R) + query(rs, z + 1, r, L, R);
    }
} seg;

int main() {
    int n, m;
    scanf("%s", p + 1);
    n = strlen(p + 1), scanf("%d", &m);
    seg.build(1, 1, n);
    while(m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        Info result = seg.query(1, 1, n, l, r);
        //result.output();
        printf("%d\n", result.plen << 1);
    }
    return 0;
}

设计思路与复杂度分析

单次括号匹配问题可以使用栈来应对，时间复杂度为\(O(n)\)。但是此题需要多次查询，如果使用栈，则总时间复杂度为\(O(m\times n)\)，显然会超时。于是需要寻找更优秀的算法，现在已经知道查询次数是\(m\)无法优化了，所以启发我们去寻找一个将单次查询的复杂度降低一个数量级的算法。即单次查询需要从\(O(n)\)降低到\(O(logn)\)。

我们考虑分治策略，将被查询的区间二等分，那么当前区间配对括号数由左右子区间分别配对的括号数之和再加上左区间剩余左括号量与右区间剩余右括号量能够配对的数量。由此推知这是一个区间操作问题，可以使用线段树实现。

具体实现的时候，当前节点左右括号数量直接由左右子树括号数累加，而配对的括号数为分别配对的括号数之和再加上左子树剩余左括号量与右子树剩余右括号量能够配对的数量。如此复杂度降低为\(O(m\times logn)\)。

0%