Luogu P3797 妖梦斩木棒

解题思路

用线段树做这个就不用说了吧，但是要维护的东西确实很神奇。在每一个节点上都维护一个$lbkt$，表示这个区间上最靠左的右括号的位置；一个$rbkt$，表示这个区间上最靠右的左括号的位置。还有一个$sum$，表示这段区间（除去左右端点）上有几段完整的木棒。

注意如果一个区间内没有左右括号的话，那$lbkt=0,rbkt=0$

然后再考虑如何建树。首先想到的是第一个节点，它代表的区间是$1-n$，他的$lbkt$是$n$，$rbkt$是$1$。然后对于包含左右端点的区间进行一下特判，类似于第一个节点的操作，其余的就没啥好说的了，要是再不会就退群吧

这道题目唯一良心的地方就是那个单点修改，还好没给整成区间修改。那我们怎么单点修改呢？因为是单点修改，修改的时候$l=r$，所以可以很容易的确定$lbkt$和$rbkt$。如果是'X'的话，那么这两个值都是$0$。$sum$的维护也不难，修改了之后无非只有两种情况，那就是想修改了之后左右儿子多出了一段木棒。也有可能没有多处，所以只需要把左右儿子的$sum$加起来，再判断修改了之后能不能构成一段新的木棒。

询问也没啥好说的

附上代码

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define Lson (k << 1)

#define Rson (k << 1) + 1

using namespace std;

const int maxnode = 8e5+;

int n, m;

struct node {

    int l, r, sum, lbkt, rbkt;

}tree[maxnode];

inline void build(int k, int ll, int rr) {

    tree[k].l = ll, tree[k].r = rr;

    if(k == ) { tree[k].sum = , tree[k].lbkt = n, tree[k].rbkt = ; }

    else {

        tree[k].sum = ;

        if(tree[k].l == ) tree[k].rbkt = ;

        if(tree[k].r == n) tree[k].lbkt = n;

    }

    if(tree[k].l == tree[k].r) return ;

    int mid = (tree[k].l + tree[k].r) >> ;

    build(Lson, tree[k].l, mid), build(Rson, mid+, tree[k].r);

}

inline void update(int k, int x, int y) {

    if(tree[k].l == tree[k].r && tree[k].l == x) {

        if(y == ) tree[k].rbkt = x, tree[k].lbkt = ;

        if(y == ) tree[k].rbkt = , tree[k].lbkt = ;

        if(y == ) tree[k].rbkt = , tree[k].lbkt = x;

        return ;

    }

    int mid = (tree[k].l + tree[k].r) >> ;

    if(mid >= x) update(Lson, x, y);

    if(mid < x) update(Rson, x, y);

    tree[k].sum = tree[Lson].sum + tree[Rson].sum;

    tree[k].sum += min(tree[Lson].rbkt, ) * min(tree[Rson].lbkt, );

    if(tree[Lson].lbkt > ) tree[k].lbkt = tree[Lson].lbkt;

    else if(tree[Lson].rbkt ==  and tree[Lson].sum == )

        tree[k].lbkt = tree[Rson].lbkt;

    else tree[k].lbkt = ;

    if(tree[Rson].rbkt > ) tree[k].rbkt = tree[Rson].rbkt;

    else if(tree[Rson].lbkt ==  and tree[Rson].sum == )

        tree[k].rbkt = tree[Lson].rbkt;

    else tree[k].rbkt = ;

}

inline int queryl(int k, int l, int r) {

    if(tree[k].lbkt <= r && tree[k].lbkt >= l) return tree[k].lbkt;

    else return ;

}

inline int queryr(int k, int l, int r) {

    if(tree[k].rbkt <= r && tree[k].rbkt >= l) return tree[k].rbkt;

    else return ;

}

inline int Query(int k, int l, int r) {

    if(tree[k].l > r || tree[k].r < l) return ;

    if(tree[k].l >= l && tree[k].r <= r) return tree[k].sum;

    int ans = Query(Lson, l, r) + Query(Rson, l, r);

    ans += min(queryl(Rson, l, r), ) * min(queryr(Lson, l, r), );

    return ans;

}

int main() {

    scanf("%d%d", &n, &m);

    build(, , n);

    int x, y, z;

    char ch;

    for(int i=; i<=m; i++) {

        scanf("%d", &z);

        if(z == ) {

            cin>>x; cin>>ch;

            if(ch == '(') y = ;

            if(ch == 'X') y = ;

            if(ch == ')') y = ;

            update(, x, y);

        }

        else {

            cin>>x>>y;

            printf("%d\n", Query(, x, y));

        }

    }

    return ;

}