正题

---

大意

有n个括号，有左有右，求一个区间内有多少个括号不能相互匹配。中间会改变某些括号的方向。

---

解题思路

线段树维护两个数lm(left moreleftmore),rm(right morerightmore)分别表示这个区间内多余的左括号和多余的右括号（是能相互匹配的，如“)()(”这两个括号就不能相互匹配）。然后我们需要考虑两段区间如何合并。

我们想一下，已经计算好的一个区间中的左括号是不能和右括号相互匹配的，但是在它右边的区间中的所有多余的右括号都能和这个区间中的左括号相互匹配，所以我们可以得到：

t[x].lm=t[x∗2+1].lm+max(0,t[x∗2].lm−t[x∗2+1].rm)t[x].lm=t[x∗2+1].lm+max(0,t[x∗2].lm−t[x∗2+1].rm)
相反，在这个区间的左边的区间内所有的左边括号都可以和这个区间内的右括号相互匹配：
t[x].rm=t[x∗2].rm+max(0,t[x∗2+1].rm−t[x∗2].lm)t[x].rm=t[x∗2].rm+max(0,t[x∗2+1].rm−t[x∗2].lm)
然后维护查询修改都是正常操作

---

代码

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #define MN 150001 using namespace std; struct tnode{int rm,lm,l,r; }t[MN*4]; int n,m,x,y,anl,anr,zal,zar; char c[7],str[MN]; void build(int x,int l,int r){t[x].l=l;t[x].r=r;if (l==r) {t[x].lm=str[l]=='('?1:0;t[x].rm=str[l]==')'?1:0;return;}int mid=(l+r)>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r);t[x].lm=t[x*2+1].lm+max(0,t[x*2].lm-t[x*2+1].rm);t[x].rm=t[x*2].rm+max(0,t[x*2+1].rm-t[x*2].lm);//维护 } void updata(int x,int z) {if (t[x].l==z&&t[x].r==z){t[x].rm^=1,t[x].lm^=1;return;}int mid=(t[x].l+t[x].r)>>1;if (z<=mid) updata(x<<1,z);else updata(x<<1|1,z);t[x].lm=t[x*2+1].lm+max(0,t[x*2].lm-t[x*2+1].rm);t[x].rm=t[x*2].rm+max(0,t[x*2+1].rm-t[x*2].lm);//维护 } void find(int x,int l,int r) {if (t[x].l==l&&t[x].r==r){anl+=max(0,t[x].rm-anr);anr=t[x].lm+max(0,anr-t[x].rm);//累计return;}int mid=(t[x].l+t[x].r)>>1;if (r<=mid) find(x<<1,l,r);else if (l>mid) find(x<<1|1,l,r);else {find(x<<1,l,mid);find(x<<1|1,mid+1,r);} } int main() {//freopen("elf.in","r",stdin);//freopen("elf.out","w",stdout);scanf("%d%d",&n,&m);scanf("%s",str+1);build(1,1,n);for (int i=1;i<=m;i++){scanf("%s",c+1);if (c[1]=='Q'){scanf("%d%d",&x,&y);find(1,x,y);printf("%d %d\n",anl,anr);anl=0;anr=0;}else{scanf("%d",&x);updata(1,x);}} }

总结

以上是生活随笔为你收集整理的jzoj4273-圣章-精灵使的魔法语【线段树】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。