题解 P3797 【妖梦斩木棒】线段树

**博客[传送门](http://www.wjyyy.top/798.html)** ## 题解：    表面看上去是一个**单点修改，区间查询**的线段树，可是维护木棍个数是个问题。可以看出，如果把木棍看作线段树的区间，而拼出来的木棍中间不能出现多余的'('或')'，那么我们计算线段树区间和时，只需要把两边原本就有的木棍数加起来，并判断左区间**最右边的左括号**和右区间**最左边的右括号**之间有没有**其他括号**。如果有，则不增加，如果没有，把个数增加1。   这样一来，我们要维护的信息是：**区间内存在的完整木棍数v，最右边的左括号rl，最左边的右括号lr，最左边的左括号ll，最右边的右括号rr**。因为我们维护的是**最值**，所以当没有的时候就设为缺省值。维护最左边的，缺省值为233333（大于200000就可以）；维护最右边的，缺省值为0。这样取min或max的时候，在另一个参数有意义时，就不会有影响。    ##### 重构代码大法好。一开始准备在原来的代码上改改，后来一个小时过去实在弄不下去了直接重构。改完语法错误就过了= = ## Code： ```cpp #include<cstdio> #include<cstring> #include<algorithm> #define ls (k<<1) #define rs (k<<1|1) #define mid (l+r>>1) #define Mid (t[k].l+t[k].r>>1) using std::min; using std::max; struct node { int l,r,v,lr,rl,ll,rr; node(int l,int r) { this->l=l; this->r=r; v=0; } node(){v=0;} }t[810000]; void maintain(int k) { if(t[ls].rl>t[ls].rr&&t[rs].lr<t[rs].ll)//左区间最右边的左括号和有区间最左边的右括号中间没有其他括号 t[k].v=t[ls].v+t[rs].v+1; else t[k].v=t[ls].v+t[rs].v; t[k].ll=min(t[ls].ll,t[rs].ll);//维护最大/最小 t[k].lr=min(t[ls].lr,t[rs].lr); t[k].rr=max(t[ls].rr,t[rs].rr); t[k].rl=max(t[ls].rl,t[rs].rl); return; } int n; void build(int k,int l,int r) { t[k]=node(l,r); if(l==r) { if(l==1) { t[k].lr=233333;//l开头的缺省值为233333 t[k].rl=1;//r开头的缺省值为0 t[k].ll=1; t[k].rr=0; } else if(l==n) { t[k].lr=n; t[k].rl=0; t[k].ll=233333; t[k].rr=n; } else { t[k].lr=233333; t[k].rl=0; t[k].ll=233333; t[k].rr=0; } return; } build(ls,l,mid); build(rs,mid+1,r); maintain(k); } void change(int k,int x,char c) { if(t[k].l==t[k].r) { if(c=='(') { t[k].lr=233333; t[k].rr=0; t[k].ll=x; t[k].rl=x; } else if(c==')') { t[k].lr=x; t[k].rr=x; t[k].ll=233333; t[k].rl=0; } else { t[k].lr=233333; t[k].rr=0; t[k].ll=233333; t[k].rl=0; } return; } if(x<=Mid) change(ls,x,c); else change(rs,x,c); maintain(k); return; } int ask(int k,int l,int r) { if(t[k].l==l&&t[k].r==r) return t[k].v; if(r<=Mid) return ask(ls,l,r); else if(l>Mid) return ask(rs,l,r); if(t[ls].rl>t[ls].rr&&t[rs].lr<t[rs].ll&&l<=t[ls].rl&&r>=t[rs].lr)//记得判范围 return ask(ls,l,Mid)+1+ask(rs,Mid+1,r); else return ask(ls,l,Mid)+ask(rs,Mid+1,r); } int main() { int m,op,l,r; char c; scanf("%d%d",&n,&m); build(1,1,n); while(m--) { scanf("%d",&op); if(op==1) { scanf("%d %c",&l,&c); change(1,l,c); } else { scanf("%d%d",&l,&r); printf("%d\n",ask(1,l,r)); } } return 0; } ```