题解：CF380C Sereja and Brackets

· · 题解

补药线段树了！！发现题解区大多都是线段树的题解云云，所以来一篇经典折线模型（？）的题解。

顺便逼自己证明一下。

p.s. 关于下文提到的那个 01 串排序问题，其实也不难，不过想知道的友友可以私信找我要一下。这里就不加长篇幅了。

Solution

就我目前所见，除了括号序列之外，还有 01 串排序问题也可以用折线模型抽象。左括号 1，右括号 -1。

考虑这个区间括号抽象出来的折线。显然的前置结论就是，合法括号序列的折线必定是全部位于水平线之上的，且必定是从水平处出发，水平处结束。水平线就是 0，也即我描灰的线。

所以如下图染绿色的部分所示，这些绿色三角必定本身是一个合法括号序列了，我们可以直接删掉它们，把剩下的折线合并到一起。也即我描红的折线。

一直重复这个过程，直到折线不存在尖角向上的三角形。此时的折线要么是一条直线，要么是尖角向下的三角形。发现剩下的部分我们再怎么样也无法继续匹配了。

所以最后的答案就是区间长度 减去 剩下无法继续匹配的折线的长度。

这个长度是什么？左侧的直线长度是 -\min(0,mn)，右侧的直线长度是 h_r-mn，h_r 是结尾的折线高度，mn 是折线的最低谷。也即我描蓝的部分。

所以用 st 表维护一下区间最小值就好了。

Code

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

#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)

const int maxn = 1e6 + 5;

int n, s[maxn], st[21][maxn];

inline int qry(int l, int r){
    int k = log2(r - l + 1);
    return min(st[k][l], st[k][r - (1 << k) + 1]); 
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    string str; cin >> str;
    n = str.length(); str = " " + str;
    rep(i, 1, n) s[i] = s[i - 1] + (str[i] == '(' ? 1 : -1), st[0][i] = s[i]; 

    for(int j = 1; (1 << j) <= n; ++j) for(int i = 1; i + (1 << j) - 1 <= n; ++i)
        st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);

    int m; cin >> m;
    while(m--){
        int l, r; cin >> l >> r;
        int ans = r - l + 1, mn = min(qry(l, r) - s[l - 1], 0);
        ans -= s[r] - s[l - 1] - mn * 2;
        cout << ans << '\n';
    }
    return 0;
}

Proof

如果放完代码就结束了，可能得被喷。

为什么这样贪心是对的？

考虑调整法。如果某一次删除向上三角形时，我们留下了可以匹配的一对括号，没有直接匹配。

容易发现因为我们删除的都是尖角向上的三角形，画图就能发现在这个三角形内，不论是左括号还是右括号，和它匹配到的都是最近的、能和它匹配的右/左括号（说的不严谨，其实并不是严格最近，而是相对这个三角形以外的其他可匹配括号最近的）。

如果后面把它匹配了，匹配括号一定相对更远，所以运用调整法，把它调整到同一个三角内匹配，一定不劣。

其实线段树的底层思维也是这个啊，只是看起来自然所以没有啥题解真的去证明而已。

证得貌似不咋好，凑合一下。