解题思路
用线段树做这个就不用说了吧，但是要维护的东西确实很神奇。在每一个节点上都维护一个$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+
3;
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 ==
1) { tree[k].sum =
1, tree[k].lbkt = n, tree[k].rbkt =
1; }
else {
tree[k].sum =
0;
if(tree[k].l ==
1) tree[k].rbkt =
1;
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) >>
1;
build(Lson, tree[k].l, mid), build(Rson, mid+
1, 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 ==
1) tree[k].rbkt = x, tree[k].lbkt =
0;
if(y ==
2) tree[k].rbkt =
0, tree[k].lbkt =
0;
if(y ==
3) tree[k].rbkt =
0, tree[k].lbkt =
x;
return ;
}
int mid = (tree[k].l + tree[k].r) >>
1;
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,
1) * min(tree[Rson].lbkt,
1);
if(tree[Lson].lbkt >
0) tree[k].lbkt =
tree[Lson].lbkt;
else if(tree[Lson].rbkt ==
0 and tree[Lson].sum ==
0)
tree[k].lbkt =
tree[Rson].lbkt;
else tree[k].lbkt =
0;
if(tree[Rson].rbkt >
0) tree[k].rbkt =
tree[Rson].rbkt;
else if(tree[Rson].lbkt ==
0 and tree[Rson].sum ==
0)
tree[k].rbkt =
tree[Lson].rbkt;
else tree[k].rbkt =
0;
}
inline int queryl(
int k,
int l,
int r) {
if(tree[k].lbkt <= r && tree[k].lbkt >= l)
return tree[k].lbkt;
else return 0;
}
inline int queryr(
int k,
int l,
int r) {
if(tree[k].rbkt <= r && tree[k].rbkt >= l)
return tree[k].rbkt;
else return 0;
}
inline int Query(
int k,
int l,
int r) {
if(tree[k].l > r || tree[k].r < l)
return 0;
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),
1) * min(queryr(Lson, l, r),
1);
return ans;
}
int main() {
scanf("%d%d", &n, &
m);
build(1,
1, n);
int x, y, z;
char ch;
for(
int i=
1; i<=m; i++
) {
scanf("%d", &
z);
if(z ==
1) {
cin>>x; cin>>
ch;
if(ch ==
'(') y =
1;
if(ch ==
'X') y =
2;
if(ch ==
')') y =
3;
update(1, x, y);
}
else {
cin>>x>>
y;
printf("%d\n", Query(
1, x, y));
}
}
return 0;
}
转载于:https://www.cnblogs.com/bljfy/p/9487121.html
相关资源：数据结构—成绩单生成器
