题解 CF380C 【Sereja and Brackets】

Cylete · 2020-11-13 15:38:55 · 题解

首先[l,r]中合法的括号串长度就等于r - l + 1 - 未匹配的'(' - 未匹配的')'

考虑线段树维护一个区间内有多少未匹配的左括号和未匹配的右括号

合并的时候减去新匹配的括号数，即：

其中lson为左儿子rson为右儿子

每段区间处理完后等于删掉匹配的括号，只剩下类似 ))))(((( 的（左右括号可有可无）

inline void into() { ios::sync_with_stdio(false); }

#define int long long
#define mid ((l+r)>>1)
#define lson (o<<1)
#define rson (o<<1|1)
#define R register
#define PP pair<int, int>
#define mp(x, y) make_pair(x, y)

const int N = 1e6 + 10;

char s[N];
int n, m;
//tl未未匹配的左括号数，tr为未匹配的右括号数
int tl[N << 2], tr[N << 2];
//合并
inline void pushup(int o)
{
    tl[o] = tl[lson] + tl[rson] - min(tl[lson], tr[rson]);
    tr[o] = tr[lson] + tr[rson] - min(tl[lson], tr[rson]);
}

inline void build(int o, int l, int r)
{
    if(l == r)
    {
        if(s[l] == '(') tl[o] = 1;
        else tr[o] = 1;
        return;
    }
    build(lson, l, mid);
    build(rson, mid + 1, r);
    pushup(o);
}

inline PP ask(int o, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr) return mp(tl[o], tr[o]);
    if(qr <= mid) return ask(lson, l, mid, ql, qr);
    if(ql > mid) return ask(rson, mid + 1, r, ql, qr);
    PP ls = ask(lson, l, mid, ql, qr), rs = ask(rson, mid + 1, r, ql, qr), res;
    res.first = ls.first + rs.first - min(ls.first, rs.second);
    res.second = ls.second + rs.second - min(ls.first, rs.second);
    return res;
}

int x, y;

signed main()
{
    into();
    cin >> s + 1;
    n = strlen(s + 1);
    build(1, 1, n);
    cin >> m;
    while(m--)
    {
        cin >> x >> y;
        PP ans = ask(1, 1, n, x, y);
        cout << (y - x + 1) - ans.first - ans.second << endl;
    }
    return 0;
}