ABC350F 题解

__ryp__ · 2024-04-21 16:00:05 · 题解

这是一篇 平衡树 题解，跑得比较慢（O(n\log n)，121ms），但是思维难度较低。

题意

把括号序列从内向外展开。展开是指区间与大小写的同时反转。

输出最后的字符串，不含括号。

分析

根据“序列翻转”，我们可以想到文艺平衡树。大小写反转，无非就是在标记上简单操作一下。

怎么保证从内向外展开呢？我们可以用栈模拟括号匹配：遇到左括号就入栈当前下标，遇到右括号就从栈里弹出左括号，并且将左右括号下标存起来。

最后所有的括号都是不交的，也即，l_i \lt r_i \lt l_{i+1} \lt r_{i+1}。于是，我们按照 r - l 即括号序列的长度排序，然后挨个展开，就一定能保证是从内向外展开的。

核心代码：

for (int i = 0; i < n; i++) 
    if (s[i] == '(') q.push (i);
    else if (s[i] == ')') g.push_back(make_pair (q.top (), i)), q.pop ();
sort (begin (g), end (g), [](pi &x, pi &y) { return x.se - x.fi < y.se - y.fi; });
for (auto v : g) rev (v.fi + 2, v.se);
dfs (rt);

submission 121ms

后记：发现自己纯 nt 了。。。O(n) 简单可做。。黄愣成蓝