作为当年负责讲解splay的本蒟蒻突然发现自己不记得splay怎么打了…… 在经历了一番激烈的思想斗争后决定回来复习一下。 (因为咱突然发现6个多月过去了咱还从来没有用过平衡树系列的东西) 然后就被此题玩了个半死……
思路: 那些操作一看就是在钦定splay了…… 然后考虑如何兹瓷询问。 假设现在有一个奇怪的括号序列: ))()()(((()))(() 咱来配个对: ))(( 那么这就是咱要的答案:2/2+2/2=2。 也就是(左括号数+1)/2+(右括号数+1)/2（加一即向上取整）
如何维护消去后的左括号数和右括号数？ 令’(‘为1，’)’为-1 那么可以发现，左括号数值就是前缀和的最小值，右括号数就是后缀和的最大值。 也就是左起最小和右起最大。
考虑到几种操作，或许咱们需要维护左起最大最小、右起最大最小四个tag? 理论上是的，但其实只需要左起最大最小，一共两个tag就够了……
考虑swap,交换左起最大和右起最小，右起最大和左起最小。 只维护两个的话，左起最大会变成区间和减去原左起最小，左起最小同理。 考虑invert,交换左起最大和左起最小，右起最大和右起最小。 只维护两个的话，同时乘以-1并交换位置就好。 考虑Replace,咱认为这不需要考虑。 考虑Query,可以发现右起最大加上左起最小的值等于区间和。 然后就没有然后了……
等等你说许多题解提到了一个tag的更新顺序？ 事实上只需要在下传tag时优先Replace，并在更新时顺手清空子树的Invert标记即可~ 因为在拥有了Replace标记后，子树的Invert标记被无效化了，此时咱们再下传当前节点的有效的Invert标记，就可以不打乱顺序了~
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; const int N=1000009; int n,q,root; char s[N]; int ch[N][2],fa[N],val[N],siz[N],sum[N],tot; int up[N],down[N],rev[N],inv[N],rep[N]; inline int maxx(int a,int b){if(a>b)return a;return b;} inline int minn(int a,int b){if(a<b)return a;return b;} inline void update(int x) { siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1; sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x]; up[x]=maxx(up[ch[x][0]],up[ch[x][1]]+sum[ch[x][0]]+val[x]); down[x]=minn(down[ch[x][0]],down[ch[x][1]]+sum[ch[x][0]]+val[x]); } inline void invert(int x) { inv[x]^=1; val[x]=-val[x]; sum[x]=-sum[x]; down[x]=-down[x]; up[x]=-up[x]; swap(up[x],down[x]); } inline void replace(int x,int ty) { inv[x]=0; rep[x]=ty; if(ty==1) { val[x]=1;sum[x]=siz[x]; up[x]=siz[x];down[x]=0; } else { val[x]=-1;sum[x]=-siz[x]; up[x]=0;down[x]=-siz[x]; } } inline void reverse(int x) { rev[x]^=1; up[x]=sum[x]-up[x]; down[x]=sum[x]-down[x]; swap(up[x],down[x]); } inline void push(int x) { if(rev[x]) { swap(ch[x][0],ch[x][1]); reverse(ch[x][0]); reverse(ch[x][1]); rev[x]=0; } if(rep[x]) { replace(ch[x][0],rep[x]); replace(ch[x][1],rep[x]); rep[x]=0; } if(inv[x]) { invert(ch[x][0]); invert(ch[x][1]); inv[x]=0; } } inline void prepush(int x) { if(fa[x]) prepush(fa[x]); push(x); } inline int find(int x,int k) { push(x); if(k==siz[ch[x][0]]+1) return x; else if(k<=siz[ch[x][0]]) return find(ch[x][0],k); else return find(ch[x][1],k-siz[ch[x][0]]-1); } inline void rotate(int x) { int y=fa[x],z=fa[y]; int l=(ch[y][1]==x); if(z)ch[z][ch[z][1]==y]=x; fa[x]=z;fa[y]=x;fa[ch[x][l^1]]=y; ch[y][l]=ch[x][l^1];ch[x][l^1]=y; update(y);update(x); } inline int build(int l,int r) { if(l>r)return 0; int mid=l+r>>1,now=++tot; val[now]=(s[mid]=='('?1:-1); ch[now][0]=build(l,mid-1); ch[now][1]=build(mid+1,r); fa[ch[now][0]]=fa[ch[now][1]]=now; update(now); return now; } inline void splay(int x,int target=0) { prepush(x); while(fa[x]!=target) { int y=fa[x],z=fa[y]; if(z!=target) { if((ch[y][0]==x)^(ch[z][0]==y))rotate(x); else rotate(y); } rotate(x); } if(!target) root=x; update(x); } int main() { scanf("%d%d",&n,&q); scanf("%s",s+1); root=build(0,n+1); for(int i=1,l,r;i<=q;i++) { scanf("%s%d%d",s+1,&l,&r); l=find(root,l); r=find(root,r+2); splay(l); splay(r,root); if(s[1]=='R') { scanf("%s",s+1); replace(ch[r][0],s[1]=='('?1:-1); } else if(s[1]=='S') reverse(ch[r][0]); else if(s[1]=='I') invert(ch[r][0]); else printf("%d\n",(-down[ch[r][0]]+1)/2+(sum[ch[r][0]]+(-down[ch[r][0]]+1)/2*2)/2); update(l); update(r); } return 0; }