Description

JSOI 教练组按如下定义配对的括号序列:

  1. \(()\) 是配对的括号序列.
  2. 若 \(A\) 是配对的括号序列, 则 \((A)\) 也是配对的括号序列.
  3. 若 \(A, B\) 是配对的括号序列, 则 \(AB\) 也是配对的括号序列.

例如, 以下是配对的括号序列:

\[(())()()((()())), ((((())))), ()()()()(())\]

以下则是不配对的括号序列:

\[)()()()()()(, (())((), (())(()))()(()\]

繁多的括号总是让 JSOI 教练组看花眼, 难以分辨一个很长的括号序列究竟是不是配对的, 所以他请你编写一个程序, 输入一个括号序列, 并能够完成以下三种操作:

  1. 询问将 \(A[x], A[x+1], \ldots, A[y]\) 形成的括号序列修改为配对的括号序列, 至少 需要修改多少个括号.
  2. 将 \(A[x], A[x+1], \ldots, A[y]\) 的子序列执行反转, 所有的 \((\) 修改为 \()\), 所有 的 \()\) 修改为 \((\).
  3. 将 \(A[x], A[x+1], \ldots, A[y]\) 的子序列执行翻转, 原子序列被 \(A[y], A[y-1], \ldots, A[x]\) 替代.

Input

输入数据的第一行包含两个整数 \(n\) 和 \(Q\), 分别表示括号序列的长度, 以及操作的个数.

第二行包含一个长度为 \(n\) 的括号序列.

接下来 \(Q\) 行, 每行三个整数 \(t, x, y\), 分别表示操作的类型、操作的开始位置和操作的结束位置, 输入数据保证 \(x \leq y\). 其中 \(t = 0\) 表示询问操作、\(t = 1\) 表示反转 操作、\(t = 2\) 表示翻转操作.

Output

对于每一个询问操作, 输出一行, 表示将括号序列的该子序列修改为配对, 所需的最少改动个数.

Sample Input

6 3
)(())(
0 1 6
0 1 4
0 3 4

Sample Output

2
2
0

Data Range

对于 100% 的数据, 满足:\(0 \lt n, q \leq 10^5\)

Explanation

原文链接:http://blog.csdn.net/lych_cys/article/details/50700277

首先, 对于一个括号序列, 例如:\(())()(((\), 我们把可以匹配的去掉, 就变成了:\()(((\). 换句话说, 对于一般的括号序列, 化简以后就变成了左边 \(x\) 个 \()\), 右边 \(y\) 个 \((\). 显然 \(x + y\) 为偶数, 我们可以发现此时答案为 \(\frac{x}{2}+\frac{y}{2}\) (\(x, y\) 为偶数) 或者 \(\frac{x}{2}+1+\frac{y}{2}+1\) (\(x, y\) 为奇数), 合并一下就是 \([\frac{x+1}{2}]+[\frac{y+1}{2}]\).

关键是对于序列 \((l, r)\),\(x\) 和 \(y\) 怎么求. 实际上我们发现 \(x\) 就是求左端点为 \(l\), 右端点 \(\leq r\) 时, 序列中右括号比左括号多的个数的最大值 \((\gt 0)\). 换句话说, 如果令 \(( = 1, ) = -1\), 实际上 \(x\) 就是最小左子段和,\(y\) 就是最大右子段和. 由于 还有反转 (不是翻转) 操作, 因此还需要维护最大左子段和和最小右子段和. 为了维护最小 最大子段和, 还需要维护一个区间和.

顺便吐槽一下, Splay 调了好久对拍也没有问题, 最后发现是 Query 写错了 (向下取整) 然后发现实在是太制杖...... QwQ

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define SWTAPI inline
#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define range(_begin,_end) rep(_,_begin,_end)
using namespace std;
typedef long long lli;
const int maxn = 200100;

class SplayTree
{
public:
    int arr_i[maxn][12];
    #define lc(_x) arr_i[_x][0]
    #define rc(_x) arr_i[_x][1]
    #define ch(_x,_y) arr_i[_x][_y]
    #define par(_x) arr_i[_x][2]
    #define size(_x) arr_i[_x][3]
    #define val(_x) arr_i[_x][4]
    #define vsm(_x) arr_i[_x][5]
    #define lmn(_x) arr_i[_x][6]
    #define rmn(_x) arr_i[_x][7]
    #define lmx(_x) arr_i[_x][8]
    #define rmx(_x) arr_i[_x][9]
    #define lazyrev(_x) arr_i[_x][10]
    #define lazyinv(_x) arr_i[_x][11]
    int root, ncnt;
    SWTAPI int make_node(int v)
    {
        int p = ++ncnt;
        lc(p) = rc(p) = par(p) = 0;
        size(p) = 1, val(p) = vsm(p) = v;
        lmn(p) = rmn(p) = min(p, 0);
        lmx(p) = rmx(p) = max(p, 0);
        lazyrev(p) = lazyinv(p) = 0;
        return p;
    }
    SWTAPI void mark_rev(int p)
    {
        if (!p) return ;
        lazyrev(p) ^= 1;
        swap(lmn(p), rmn(p));
        swap(lmx(p), rmx(p));
        return ;
    }
    SWTAPI void mark_inv(int p)
    {
        if (!p) return ;
        lazyinv(p) ^= 1;
        swap(lmn(p), lmx(p));
        swap(rmn(p), rmx(p));
        val(p) = -val(p); vsm(p) = -vsm(p);
        lmn(p) = -lmn(p); lmx(p) = -lmx(p);
        rmn(p) = -rmn(p); rmx(p) = -rmx(p);
        return ;
    }
    SWTAPI void update_lazy(int p)
    {
        size(p) = size(lc(p)) + 1 + size(rc(p));
        vsm(p) = vsm(lc(p)) + val(p) + vsm(rc(p));
        lmn(p) = min(lmn(lc(p)), vsm(lc(p)) + val(p) + lmn(rc(p)));
        lmx(p) = max(lmx(lc(p)), vsm(lc(p)) + val(p) + lmx(rc(p)));
        rmn(p) = min(rmn(rc(p)), vsm(rc(p)) + val(p) + rmn(lc(p)));
        rmx(p) = max(rmx(rc(p)), vsm(rc(p)) + val(p) + rmx(lc(p)));
        return ;
    }
    SWTAPI void push_down(int p)
    {
        if (lazyrev(p)) {
            swap(lc(p), rc(p));
            mark_rev(lc(p)); mark_rev(rc(p));
            lazyrev(p) = false;
        }
        if (lazyinv(p)) {
            mark_inv(lc(p)); mark_inv(rc(p));
            lazyinv(p) = false;
        }
        return ;
    }
    SWTAPI void rotate(int p)
    {
        int q = par(p), g = par(q);
        push_down(q);
        push_down(p);
        int x = p == rc(q), y = q == rc(g);
        ch(q, x) = ch(p, !x); if (ch(q, x)) par(ch(q, x)) = q;
        ch(p, !x) = q; par(q) = p;
        if (g) ch(g, y) = p; par(p) = g;
        update_lazy(q);
        update_lazy(p);
        return ;
    }
    SWTAPI void splay(int p, int t)
    {
        for (int q = 0; (q = par(p)) && q != t; rotate(p))
            if (par(q) && par(q) != t)
                rotate((p == rc(p)) == (q == rc(par(q))) ? q : p);
        if (t == 0) root = p;
        return ;
    }
    SWTAPI int find(int sz)
    {
        int p = root;
        while (true) {
            push_down(p);
            if (sz <= size(lc(p))) {
                p = lc(p);
                continue;
            } sz -= size(lc(p));
            if (sz <= 1) {
                return p;
            } sz -= 1;
            p = rc(p);
        }
        return p;
    }
    SWTAPI int query(int l, int r)
    {
        int lp = find(l), rp = find(r + 2);
        splay(lp, 0);
        splay(rp, root);
        int p = lc(rp);
        // update_lazy(p);
        // int res = int((- lmn(p) + 1) / 2)
        //     + int((rmx(p) + 1) / 2);
        int res = (rmx(p) + 1) / 2 - (lmn(p) - 1) / 2;
        return res;
    }
    SWTAPI void inverse(int l, int r)
    {
        int lp = find(l), rp = find(r + 2);
        splay(lp, 0);
        splay(rp, root);
        int p = lc(rp);
        mark_inv(p);
        splay(p, 0);
        return ;
    }
    SWTAPI void reverse(int l, int r)
    {
        int lp = find(l), rp = find(r + 2);
        splay(lp, 0);
        splay(rp, root);
        int p = lc(rp);
        mark_rev(p);
        splay(p, 0);
        return ;
    }
    SWTAPI int dfs_build(int l, int r, char str[])
    {
        if (l > r)
            return 0;
        int mid = (l + r) >> 1;
        int val = str[mid] == '(' ? 1 : -1;
        int p = make_node(val);
        lc(p) = dfs_build(l, mid - 1, str);
        rc(p) = dfs_build(mid + 1, r, str);
        range(0, 1) if (ch(p, _)) par(ch(p, _)) = p;
        update_lazy(p);
        return p;
    }
    SWTAPI void build_tree(int n, char str[])
    {
        ncnt = 0;
        str[0] = str[n + 1] = '-';
        root = dfs_build(0, n + 1, str);
        return ;
    }
} st;

int n, Q;
char str[maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &Q);
    scanf("%s", str + 1);
    st.build_tree(n, str);
    for (int idx = 1; idx <= Q; idx++) {
        int t, l, r;
        scanf("%d%d%d", &t, &l, &r);
        if (t == 0) {
            int res = st.query(l, r);
            printf("%d\n", res);
        } else if (t == 1) {
            st.inverse(l, r);
        } else if (t == 2) {
            st.reverse(l, r);
        }
    }
    return 0;
}