题目大意:
给你一段长度为$n$的括号序列,有以下操作:一、Change x:将x处的括号反向;二、Query x y:查询欲使[x,y]内的括号序列合法,至少要从左端右端分别添加几个括号.
solution:
线段树板子,注意以下更新即可:
inline node update(node a,node b){node wn;wn._=a._+max(0,b._-a.__);wn.__=b.__+max(0,a.__-b._);return wn;}
code:
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<queue> #define R register #define next exnttttttttt #define debug puts("mlg") using namespace std; typedef int ll; typedef long double ld; typedef unsigned long long ull; inline ll read(); inline void write(ll x); inline void writesp(ll x); inline void writeln(ll x); ll n,m; bool c[200000]; struct node{ ll _,__; }t[800000]; inline node update(node a,node b){node wn;wn._=a._+max(0,b._-a.__);wn.__=b.__+max(0,a.__-b._);return wn;} inline void build(ll p,ll l,ll r){ if(l==r){ if(c[l])t[p]._=1; else t[p].__=1; return; } ll mid=l+r>>1; build(p<<1,l,mid);build(p<<1|1,mid+1,r); t[p]=update(t[p<<1],t[p<<1|1]); } inline void change(ll p,ll l,ll r,ll goal){ if(l==r){ swap(t[p]._,t[p].__);return; } ll mid=l+r>>1; if(goal<=mid) change(p<<1,l,mid,goal); else change(p<<1|1,mid+1,r,goal); t[p]=update(t[p<<1],t[p<<1|1]); } inline node query(ll p,ll l,ll r,ll goalL,ll goalR){ if(goalL<=l&&r<=goalR) return t[p]; ll mid=l+r>>1; if(goalL>mid) return query(p<<1|1,mid+1,r,goalL,goalR); if(goalR<=mid) return query(p<<1,l,mid,goalL,goalR); node x=query(p<<1,l,mid,goalL,goalR),y=query(p<<1|1,mid+1,r,goalL,goalR); return update(x,y); } int main(){ n=read();m=read(); for(R ll i=1;i<=n;i++){ char wn=getchar(); while(wn!='('&&wn!=')') wn=getchar(); c[i]=wn==')'; } build(1,1,n); while(m--){ char wn=getchar(); while(wn!='C'&&wn!='Q') wn=getchar(); if(wn=='C'){ ll x=read(); change(1,1,n,x); } else{ ll x=read(),y=read(); node ans=query(1,1,n,x,y); writesp(ans._);writeln(ans.__); } } } inline ll read(){ll x=0,t=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*t;} inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x<=9){putchar(x+'0');return;}write(x/10);putchar(x%10+'0');} inline void writesp(ll x){write(x);putchar(' ');} inline void writeln(ll x){write(x);putchar(' ');}