2024昆明区域赛 B. Brackets 题解

B. Brackets

题目翻译

​ 题目给我们一个长度为n的括号序列，该括号序列包含4种括号(), [], {}, <>。一个合法的括号序列的定义是LxR，L和R是同种类的括号的左右括号，x是一个合法的括号序列，x = y1y2，y1y2为两个合法的括号序列。题目还给我们m个子区间，我们需要计算这些子区间的括号序列进行两两匹配最多可以形成多少对合法的括号序列。(gym原题链接,复制粘贴前往 https://codeforces.com/gym/105588/problem/B)

思路

​ 首先我们通过观察题目的合法括号序列的性质可以发现，对于一个合法的括号序列，如果我们将其拆分成两半，那么要么两半初始都是合法的，要么左半去掉已经匹配的可以缩成一系列的左括号，右半也是同理。考虑吧如何处理出每个区间是什么样的情况，我们继续观察发现对于左半的情况我们可以直接使用括号栈来维护前缀种待匹配的左括号，在每个右端点时考虑区间是否可以作为左半边，当出现无法匹配的位置时我们需要清空栈并且标记1到i（i为当前考虑的位置），这些位置均不可以作为区间的左端点。同时我们呢注意到对于产生匹配括号的区间[l, r]，[l + 1, r]都不可以作为左端点，因为这样一定会剩下一个右括号多出来。对于每个区间还有什么样的括号等待着匹配我们可以直接字符串哈希即可快速解决。

​ 具体实现方面，我使用线段树来标记哪些点不可以作为左端点，然后对于括号栈同时维护下标，通过二分查找区间的待匹配括号哈希，同时动态维护括号栈的前缀哈希值。最后对于作为右半的括号，我们可以把括号序列和区间翻转，当作左半的情况再左一次。最后计算答案，注意已经匹配的区间不要数重复。

代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
template<class T>
class SegmentTree{
private:
    int n;
    struct node{
        T val;
    };
    std::vector<node> tree;
    std::vector<T> tag;
    std::vector<T> a;
 
    int ls(int p){
        return p << 1;
    }
 
    int rs(int p){
        return p << 1 | 1;
    }
 
    node merge(node a, node b){
        auto res = node();
        res.val = a.val + b.val;
        return res;
    }
 
    void push_up(int p){
        tree[p] = merge(tree[ls(p)], tree[rs(p)]);
    }
    
    void build(int p, int pl, int pr){
        if(pl == pr){
            tree[p] = node();
            tree[p].val = a[pl];
            return;
        }
        int mid = (pl + pr) >> 1;
        build(ls(p), pl, mid);
        build(rs(p), mid + 1, pr);
        push_up(p);
    }
 
    void addtag(int p, int pl, int pr, T d){
        tag[p] += d;
        tree[p].val += (pr - pl + 1) * d;
    }
 
    void push_down(int p, int pl, int pr){
        if(tag[p]){
            int mid = (pr + pl) >> 1;
            addtag(ls(p), pl, mid, tag[p]);
            addtag(rs(p), mid + 1, pr, tag[p]);
            tag[p] = 0;
        }
    }
 
    void update(int L, int R, int p, int pl, int pr, T d){
        if(L <= pl && pr <= R){
            addtag(p, pl, pr, d);
            return;
        }
        push_down(p, pl, pr);
        int mid = (pl + pr) >> 1;
        if(L <= mid)
            update(L, R, ls(p), pl, mid, d);
        if(R > mid)
            update(L, R, rs(p), mid + 1, pr, d);
        push_up(p);
    }
 
    node query(int L, int R, int p, int pl, int pr){
        if(L <= pl && pr <= R)
            return tree[p];
        push_down(p, pl, pr);
        int mid = (pl + pr) >> 1;
        if(L <= mid && R > mid)
            return merge(query(L, R, ls(p), pl, mid), query(L, R, rs(p), mid + 1, pr));
        if(L <= mid)
            return query(L, R, ls(p), pl, mid);
        if(R > mid)
            return query(L, R, rs(p), mid + 1, pr);
    }
 
public:
 
    void update(int L, int R, T d){
        update(L, R, 1, 1, n, d);
    }
 
    node query(int L, int R){
        return query(L, R, 1, 1, n);
    }
 
    SegmentTree(int len){
        n = len;
        tree.assign(n << 2, node());
        tag.assign(n << 2, 0);
    }
 
    SegmentTree(std::vector<T> cur){
        //cur 是 1序列
        int len = cur.size() - 1;
        n = len;
        tree.assign(n << 2, node());
        tag.assign(n << 2, 0);
        a = cur;
        build(1, 1, n);
    }
};

int N = 5e5;
constexpr ull PP = 131;
std::vector<ull> P;

void init(){
    P.assign(N + 1, 1);
    for(int i = 1; i <= N; i++)
        P[i] = P[i - 1] * PP;
}

void solve(){
    int n, m;
    std::cin >> n >> m;
    std::string s;
    std::cin >> s;
    s = "@" + s;

    std::vector<std::pair<int, int>> ask(m + 1);
    std::vector<std::vector<std::pair<int, int>>> pos(n + 1);
    for(int i = 1; i <= m; i++){
        std::cin >> ask[i].ff >> ask[i].ss;
        pos[ask[i].ss].push_back({ask[i].ff, i});
        //std::cerr << s.substr(ask[i].ff, ask[i].ss - ask[i].ff + 1) << endl;
    }

    std::deque<ull> stkhash;
    std::vector<char> stk;
    std::vector<int> ind;

    auto check = [&](char c){
        if(stk.size() == 0)
            return false;
        return ((c == ')' && stk.back() == '(') || (c == ']' && stk.back() == '[')
                || (c == '}' && stk.back() == '{') || (c == '>' && stk.back() == '<'));
    };

    std::map<ull, int> mp[2];

    int zero = 0;

    auto work = [&](int mode){
        ind.clear();
        stkhash.clear();
        stk.clear();
        auto seg = SegmentTree<int>(n + 1);
    
        for(int i = 1; i <= n; i++){
            if(s[i] == '(' || s[i] == '[' || s[i] == '{' || s[i] == '<'){
                stk.push_back(s[i]);
                ind.push_back(i);
                ull val = 0;
                if(stkhash.size())
                    val = stkhash.back();
                val = val * PP + s[i];
                stkhash.push_back(val);
            }
            else{
                if(check(s[i])){
                    int right = i;
                    int left = ind.back();
                    //除了匹配括号的左括号下标，其余都不可以作为左端点
                    seg.update(left + 1, right, 1);
                    stk.pop_back();
                    ind.pop_back();
                    stkhash.pop_back();
                }
                else{
                    seg.update(1, i, 1);
                    ind.clear();
                    stkhash.clear();
                    stk.clear();
                }
            }

            for(auto&[l, id] : pos[i]){
                if(seg.query(l, l).val == 0){
                    int left = l;
                    int right = i;

                    int hasleft = std::lower_bound(ind.begin(), ind.end(), left) - ind.begin();
                    int hasright = std::upper_bound(ind.begin(), ind.end(), right) - ind.begin();
                    hasright -= 1;

                    if(hasright >= hasleft){
                        ull pre = (hasleft == 0 ? 0 : stkhash[hasleft - 1]);
                        int len = hasright - hasleft + 1;
                        ull hash = stkhash[hasright] - pre * P[len];
                        mp[mode][hash] += 1;
                    }
                    else if(mode == 0){
                        //此时一定是区间不包含任何待匹配段，mode == 0时计数
                        zero += 1;
                    }
                }
            }
        }
    };

    work(0);    //mode 0 for left
    pos = std::vector<std::vector<std::pair<int, int>>>(n + 1);
    for(int i = 1; i <= m; i++){
        int r = n + 1 - ask[i].ff;
        int l = n + 1 - ask[i].ss;
        pos[r].push_back({l, i});
    }
    auto last = s;
    for(int i = 1; i <= n; i++){
        int need = n + 1 - i;
        char c;
        if(last[need] == ')')
            c = '(';
        if(last[need] == '(')
            c = ')';
        if(last[need] == ']')
            c = '[';
        if(last[need] == '[')
            c = ']';
        if(last[need] == '}')
            c = '{';
        if(last[need] == '{')
            c = '}';
        if(last[need] == '>')
            c = '<';
        if(last[need] == '<')
            c = '>';
        s[i] = c;
    }
    work(1);

    int ans = 0;
    for(auto[hash, num] : mp[0]){
        int oth = mp[1][hash];
        ans += std::min(num, oth);
    }
    ans += zero / 2;

    std::cout << ans << endl;
}