【BZOJ】2329:[HNOI 2011]括弧修復-splay
3143 ワード
転送ドア:bzoj 2329 p u s h u p pushup pushup书き间违えdebug午后...惨めでした〒▽〒
このブログははっきり書いてあります...
操作4には、余分な一致しない括弧をすべて取り出すか、そうであるか)(((())))(((()))))))((の形式、またはすべて((またはすべて)であるか)という特殊な性質がある.余分な((((の個数はx x x x,))の個数をy y yとし,答えは⌈x 2⌉+⌈y 2⌉lceilfrac x 2rceil+lceilfracy 2rceil+
'('=−1,')'=1'('=−1,')'=1'('=−1,')'=1,y=y=y=プレフィックス最大値,y=y=y=接尾辞最小値の絶対値とする.
具体的にはコードを見てみましょう.
問題解
このブログははっきり書いてあります...
操作4には、余分な一致しない括弧をすべて取り出すか、そうであるか)(((())))(((()))))))((の形式、またはすべて((またはすべて)であるか)という特殊な性質がある.余分な((((の個数はx x x x,))の個数をy y yとし,答えは⌈x 2⌉+⌈y 2⌉lceilfrac x 2rceil+lceilfracy 2rceil+
'('=−1,')'=1'('=−1,')'=1'('=−1,')'=1,y=y=y=プレフィックス最大値,y=y=y=接尾辞最小値の絶対値とする.
具体的にはコードを見てみましょう.
コード#コード#
#include
using namespace std;
const int N=1e5+100;
int n,m,rt;
char ini[N];
namespace Splay{
#define lc(x) t[(x)].ch[0]
#define rc(x) t[(x)].ch[1]
#define F(x) t[(x)].fa
#define L lc(x)
#define R rc(x)
int cnt,stk[N],top;
struct node{
int fa,ch[2];
int rv,st,op,sz,v;
int lx,rx,sum;
}t[N];
inline void pushup(int x)
{
if(!x) return;
t[x].sz=t[L].sz+t[R].sz+1;
t[x].sum=t[L].sum+t[x].v+t[R].sum;
t[x].lx=max(t[L].lx,t[L].sum+t[x].v+t[R].lx);
t[x].rx=max(t[R].rx,t[R].sum+t[x].v+t[L].rx);
}
inline void colst(int x,int vl){
t[x].rv=t[x].op=0;t[x].st=t[x].v=vl;t[x].sum=vl*t[x].sz;
t[x].lx=t[x].rx=max(0,t[x].sum);
}
inline void colrv(int x){swap(L,R);swap(t[x].lx,t[x].rx);t[x].rv^=1;}
inline void colop(int x){
int res=t[x].lx;t[x].lx=t[x].rx-t[x].sum;t[x].rx=res-t[x].sum;
t[x].sum=-t[x].sum;t[x].v=-t[x].v;t[x].op^=1;
}
inline void pushdown(int x)
{
if(t[x].st){if(L) colst(L,t[x].st);if(R) colst(R,t[x].st);t[x].st=0;}
if(t[x].rv){if(L) colrv(L);if(R) colrv(R);t[x].rv=0;}
if(t[x].op){if(L) colop(L);if(R) colop(R);t[x].op=0;}
}
int build(int l,int r,int fr)
{
if(l>r) return 0;
int x=(l+r)>>1,cur=++cnt;t[cur].fa=fr;
t[cur].v=(ini[x]=='(')?(-1):1;
lc(cur)=build(l,x-1,cur);rc(cur)=build(x+1,r,cur);
pushup(cur);return cur;
}
inline void rotate(int x)
{
int y=F(x),z=F(y),dr=(rc(y)==x);
t[y].ch[dr]=t[x].ch[dr^1];if(t[y].ch[dr]) F(t[y].ch[dr])=y;
F(y)=x;t[x].ch[dr^1]=y;F(x)=z;
if(z) t[z].ch[(rc(z)==y)]=x;pushup(y);pushup(x);
}
inline void splay(int x,int gl)
{
if(x==gl || F(x)==gl) return;
if(!gl) rt=x;int y,z;top=0;
for(y=x;y!=gl;y=F(y)) stk[++top]=y;
for(;top;--top) pushdown(stk[top]);
for(;F(x)!=gl;rotate(x)){
y=F(x);z=F(y);
if(z!=gl) ((rc(z)==y)^(rc(y)==x))?rotate(x):rotate(y);
}
pushup(x);
}
inline int kth(int kk)
{
for(int u=rt;;){
pushdown(u);
if(t[lc(u)].sz+1==kk) return u;
if(kk>t[lc(u)].sz) {kk-=(t[lc(u)].sz+1);u=rc(u);}
else u=lc(u);
}
}
}
using namespace Splay;
int main(){
int i,j,x,y,z;
scanf("%d%d%s",&n,&m,ini+1);
ini[0]=ini[n+1]=ini[n+2]='(';rt=build(0,n+2,0);
for(i=1;i<=m;++i){
scanf("%s%d%d",ini,&x,&y);
x=kth(x);y=kth(y+2);
splay(x,0);splay(y,rt);z=lc(y);
if(ini[0]=='R'){scanf("%s",ini);colst(z,ini[0]=='('?(-1):1);}
else if(ini[0]=='S') colrv(z);
else if(ini[0]=='I') colop(z);
else printf("%d
",((t[z].lx+1)>>1)+((t[z].lx-t[z].sum+1)>>1));
pushup(y);pushup(x);
}
return 0;
}