题解 - Codeforces 380C Sereja and Brackets

题意

每次询问一个区间的最大合法括号子序列长度。

分析

一般遇到合法括号序列，很多时候可以直接转化：

每个左括号视为 $1$，右括号视为 $-1$。合法的序列中每个前缀和不为负数，且以 $0$ 结束。

所以对于一段前缀和，先考虑是否存在负数，如果存在，就去掉相应数量的右括号。

不以 $0$ 结束，就去掉相应数量的左括号。

实现

一开始就直接维护整体的前缀和。那么，把单个区间的前缀和拎出来也就简单了。

默认是整个区间长度。查找负数直接用 RMQ 找个最小值即可。

注意，去掉右括号时要对整个区间的前缀和做对应的处理。

如果此时还不以 $0$ 结尾，就再去掉对应的左括号。

那么，这道题就被转化成了一个简单 RMQ！

假设区间长度是 $n$。$r=-\min(0,\min_{i=l}^{r}\{a_i\})$，而（未经变化的）整个区间的前缀和是 $s$。

那我的结论就是 $n-r-(s+r)$。

ST 表时间复杂度 $O(n\log n+m)$，线段树可以做到 $O(n+m\log n)$。

代码

ST 表都可以跑过去。更怪异的是，如果写错 ST 表，取 $r$ 的时候不考虑最后一个元素，那么只要在 $s+r$ 那里加上绝对值也可以过（具体可以推一推式子，错解我就不赘述了）。笑死了。

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

const int MXN = 1000005;
const int MXLG = 20;
int st[MXN][MXLG], lg[MXN];
char str[MXN];
int N, M;

inline int query(int l, int r) {
  int g(lg[r - l + 1]);
  return min(st[l][g], st[r - (1 << g) + 1][g]);
}

int main() {
  cin >> (str + 1);
  N = strlen(str + 1);
  lg[1] = 0;
  for (int i(2); i <= N; ++i) lg[i] = lg[i >> 1] + 1;
  for (int i(1); i <= N; ++i) {
    if (str[i] == '(') st[i][0] = st[i - 1][0] + 1;
    else st[i][0] = st[i - 1][0] - 1;
  }
  for (int i(1); (1 << i) <= N; ++i) {
    for (int j(1); j + (1 << (i - 1)) <= N; ++j) {
      st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
    }
  }
  cin >> M;
  for (int l(0), r(0); M--; ) {
    cin >> l >> r;
    int nmin(-min(query(l, r) - st[l - 1][0], 0));
    cout << (r - l + 1) - nmin - (st[r][0] - st[l - 1][0] + nmin) << endl;
  }
  return 0;
}