CF380C Sereja and Brackets

原题链接

• 题意：给出一个括号序列，然后要求 \(m < 1e5\) 个区间询问，求给出区间内，合法的括号序列的长度。
• 题解：想到了可能用线段树做，结果没想到是，线段树记录的是非合法的向左的和向右的，然后每次询问直接剪掉非合法向左和向右的即可。
• 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;


char s[N];
struct segment_tree{ 
    struct node {
        int l, r, data, L, R, suml, sumr;
    }tr[N<<2];
    struct ans {
        int suml, sumr;
    };
    inline void pushup( int p) {
        int d = min(tr[tr[p].l].sumr, tr[tr[p].r].suml);
        tr[p].suml = tr[tr[p].l].suml + tr[tr[p].r].suml - d;
        tr[p].sumr = tr[tr[p].r].sumr + tr[tr[p].l].sumr - d;
    }
    inline void build(int l, int r, int p) {
        if (l == r) {
            tr[p].L = tr[p].R = l;
            if (s[l] == ‘)‘) tr[p].suml++;
            else tr[p].sumr++;
            return;
        }
        tr[p].L = l, tr[p].R = r;
        tr[p].l = p << 1;tr[p].r = p << 1 | 1;
        int mid = l + r >> 1;
        build(l, mid, tr[p].l);
        build(mid + 1, r, tr[p].r);
        pushup(p);
    }  
    inline ans ask(int l, int r, int p) {
        if (tr[p].L >= l && tr[p].R <= r) {
            return {tr[p].suml , tr[p].sumr};
        }
        //cout << l << " " << r << endl;
        //cout << tr[p].L << "?" << tr[p].R << endl;
        //getchar();
        int mid = tr[p].L + tr[p].R >> 1;
        ans now1= {0, 0}, now2= {0, 0};
        if (l <= mid) {
             now1 = ask(l, r, tr[p].l);
        }
        if (r > mid) {
            now2 = ask(l, r, tr[p].r);
        }
        int d = min(now1.sumr, now2.suml);
        return {now1.suml + now2.suml - d, now1.sumr + now2.sumr - d};
    }
}T;

void solve() {
    cin >> (s + 1);
    int n = strlen(s + 1);
    T.build(1, n, 1); 
    int m;cin >> m;
    while (m--) {
        int l, r;cin >> l >> r;
        cout <<(r-l + 1 - (T.ask(l, r, 1).sumr +T.ask(l,r,1).suml) ) << endl;
    }
}

int main() {
    int t = 1;
    while (t--) solve();
    return 0;
}

CF380C Sereja and Brackets

原文：https://www.cnblogs.com/Xiao-yan/p/14742605.html