中和华丰建设有限责任公司网站,综合办公oa系统,抚州 提供网站建站 公司,万网空间存放两个网站正题 大意
有n个括号#xff0c;有左有右#xff0c;求一个区间内有多少个括号不能相互匹配。中间会改变某些括号的方向。 解题思路
线段树维护两个数lm(left moreleftmore),rm(right morerightmore)分别表示这个区间内多余的左括号和多余的右括号#xff08;是能相互匹配…正题 大意
有n个括号有左有右求一个区间内有多少个括号不能相互匹配。中间会改变某些括号的方向。 解题思路
线段树维护两个数lm(left moreleftmoreleft\ more),rm(right morerightmoreright\ more)分别表示这个区间内多余的左括号和多余的右括号是能相互匹配的如“)()()(”这两个括号就不能相互匹配。然后我们需要考虑两段区间如何合并。
我们想一下已经计算好的一个区间中的左括号是不能和右括号相互匹配的但是在它右边的区间中的所有多余的右括号都能和这个区间中的左括号相互匹配所以我们可以得到
t[x].lmt[x∗21].lmmax(0,t[x∗2].lm−t[x∗21].rm)t[x].lmt[x∗21].lmmax(0,t[x∗2].lm−t[x∗21].rm)
t[x].lm=t[x*2+1].lm+max(0,t[x*2].lm-t[x*2+1].rm) 相反在这个区间的左边的区间内所有的左边括号都可以和这个区间内的右括号相互匹配 t[x].rmt[x∗2].rmmax(0,t[x∗21].rm−t[x∗2].lm)t[x].rmt[x∗2].rmmax(0,t[x∗21].rm−t[x∗2].lm)
t[x].rm=t[x*2].rm+max(0,t[x*2+1].rm-t[x*2].lm) 然后维护查询修改都是正常操作代码
#includecstdio
#includealgorithm
#includecstring
#includeiostream
#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].ll;t[x].rr;if (lr) {t[x].lmstr[l](?1:0;t[x].rmstr[l])?1:0;return;}int mid(lr)1;build(x1,l,mid);build(x1|1,mid1,r);t[x].lmt[x*21].lmmax(0,t[x*2].lm-t[x*21].rm);t[x].rmt[x*2].rmmax(0,t[x*21].rm-t[x*2].lm);//维护
}
void updata(int x,int z)
{if (t[x].lzt[x].rz){t[x].rm^1,t[x].lm^1;return;}int mid(t[x].lt[x].r)1;if (zmid) updata(x1,z);else updata(x1|1,z);t[x].lmt[x*21].lmmax(0,t[x*2].lm-t[x*21].rm);t[x].rmt[x*2].rmmax(0,t[x*21].rm-t[x*2].lm);//维护
}
void find(int x,int l,int r)
{if (t[x].llt[x].rr){anlmax(0,t[x].rm-anr);anrt[x].lmmax(0,anr-t[x].rm);//累计return;}int mid(t[x].lt[x].r)1;if (rmid) find(x1,l,r);else if (lmid) find(x1|1,l,r);else {find(x1,l,mid);find(x1|1,mid1,r);}
}
int main()
{//freopen(elf.in,r,stdin);//freopen(elf.out,w,stdout);scanf(%d%d,n,m);scanf(%s,str1);build(1,1,n);for (int i1;im;i){scanf(%s,c1);if (c[1]Q){scanf(%d%d,x,y);find(1,x,y);printf(%d %d\n,anl,anr);anl0;anr0;}else{scanf(%d,x);updata(1,x);}}
}
