注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2329 (hnoi2011) 括号修复  

2013-02-16 23:19:00|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

好神的splay

集思维难度与代码难度于一体的好题啊

首先对于一个括号序列吧,我们把匹配的删掉(大家可以yy一下得到一个结论就是匹配了的不能去动它,怎么证明我也没想好),那么最后只有可能是这种情况

)))))(((((    当然可能没有左括号或者可能没有右括号

我们把左括号当成是1,右括号当成是-1

yy一下得到结论就是-最小前缀和与最大后缀和分别除以2取上整相加

所以就变成了维护最小最大前缀后缀和的经典问题

对于三种修改操作:

置为某数比较容易维护

取反操作应该是把最大前缀最小前缀交换,最大后缀最小后缀交换,最后都乘以-1(比如最小前缀是0最大前缀是3,交换后应该是最小前缀-3)

反转操作应该是把最小前缀与最小后缀交换,最大前缀与最大后缀交换

然后就是写splay了

开始写啊写,突然我意识到一个严重的问题,就是置为某数与取反、反转的顺序(我第一次遇到同时有这三种操作的题,维修序列还没去做)

于是就问啊问

总算总结出了一个方法:

1、每次修改时就赶快改了,同时置为某数的操作下,我们要把取反的标记清0。而取反的标记下,我们要把置为某数的标记取反。

2、标记下传的时候,先传取反,再传置数。

为什么这样是对的呢?

1、假设是先取反再置为某数:

我们经历了置数的修改,那么就把取反的标记清0了,这时我们只有置为某数的标记,所以答案是对的

2、假设是先置为某数再取反:

我们经历了取反的修改,此时置的数也取反了。我们先执行取反操作,没错吧?然后再执行置数操作,这时由于置数取反了一遍,所以得到的也是对的!!

很神奇吧(画外音:这是splay的常识好不好!!)

然后搞定了

 

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define MAXN 100010
using namespace std;
/*1 -> '(' -1 -> ')' */
int n,m;
/* Splay相关 */
int root,son[MAXN][2],father[MAXN],size[MAXN],sum[MAXN],v[MAXN],set[MAXN];
int minpre[MAXN],maxpre[MAXN],minsub[MAXN],maxsub[MAXN];
bool rev[MAXN],mark[MAXN],same[MAXN];
void update(int p)
{
    size[p]=size[son[p][0]]+size[son[p][1]]+1;
    sum[p]=sum[son[p][0]]+sum[son[p][1]]+v[p];
    minpre[p]=minsub[p]=maxpre[p]=maxsub[p]=0;
    if(son[p][0])
    {
        minpre[p]=min(minpre[p],minpre[son[p][0]]),maxpre[p]=max(maxpre[p],maxpre[son[p][0]]);
        minpre[p]=min(minpre[p],sum[son[p][0]]+v[p]),maxpre[p]=max(maxpre[p],sum[son[p][0]]+v[p]);
        if(son[p][1])
        {
            minpre[p]=min(minpre[p],sum[son[p][0]]+v[p]+minpre[son[p][1]]);
            maxpre[p]=max(maxpre[p],sum[son[p][0]]+v[p]+maxpre[son[p][1]]);
        }
    }
    else
    {
        minpre[p]=min(minpre[p],v[p]),maxpre[p]=max(maxpre[p],v[p]);
        if(son[p][1])  minpre[p]=min(v[p],v[p]+minpre[son[p][1]]),maxpre[p]=max(v[p],v[p]+maxpre[son[p][1]]);
    }
    if(son[p][1])
    {
        minsub[p]=min(minsub[p],minsub[son[p][1]]),maxsub[p]=max(maxsub[p],maxsub[son[p][1]]);
        minsub[p]=min(minsub[p],sum[son[p][1]]+v[p]),maxsub[p]=max(maxsub[p],sum[son[p][1]]+v[p]);
        if(son[p][0])
        {
            minsub[p]=min(minsub[p],sum[son[p][1]]+v[p]+minsub[son[p][0]]);
            maxsub[p]=max(maxsub[p],sum[son[p][1]]+v[p]+maxsub[son[p][0]]);
        }
    }
    else
    {
        minsub[p]=min(minsub[p],v[p]),maxsub[p]=max(maxsub[p],v[p]);
        if(son[p][0])  minsub[p]=min(v[p],v[p]+minsub[son[p][0]]),maxsub[p]=max(v[p],v[p]+maxsub[son[p][0]]);
    }
}
void update1(int p)
{
    rev[p]^=1;
    swap(son[p][0],son[p][1]);
    swap(minpre[p],minsub[p]),swap(maxpre[p],maxsub[p]);
}
void update2(int p)
{
    v[p]=-v[p],sum[p]=-sum[p],mark[p]^=1,set[p]=-set[p];
    swap(minpre[p],maxpre[p]),swap(minsub[p],maxsub[p]);
    minpre[p]=-minpre[p],maxpre[p]=-maxpre[p],minsub[p]=-minsub[p],maxsub[p]=-maxsub[p];
}
void update3(int p,int k)
{
    same[p]=true,set[p]=k,v[p]=k,sum[p]=k*size[p],mark[p]=false
    if(set[p]==-1)  minpre[p]=minsub[p]=sum[p],maxpre[p]=maxsub[p]=0;
    if(set[p]==1)  maxpre[p]=maxsub[p]=sum[p],minpre[p]=minsub[p]=0;
}
void push_down(int p)
{
    if(rev[p])
    {
        if(son[p][0])  update1(son[p][0]);
        if(son[p][1])  update1(son[p][1]);
        rev[p]=false;
    }
    if(mark[p])
    {
        if(son[p][0])  update2(son[p][0]);
        if(son[p][1])  update2(son[p][1]);
        mark[p]=false;
    }
    if(same[p])
    {
        if(son[p][0])  update3(son[p][0],set[p]);
        if(son[p][1])  update3(son[p][1],set[p]);
        same[p]=false;
    }
}
void Build(int l,int r)
{
    int mid=(l+r)>>1;
    if(l<mid)  Build(l,mid-1),son[mid][0]=(l+mid-1)>>1,father[(l+mid-1)>>1]=mid;
    if(mid<r)  Build(mid+1,r),son[mid][1]=(mid+1+r)>>1,father[(mid+1+r)>>1]=mid;
    update(mid);
}
void Rotate(int p,int x)
{
    int mark=p==son[x][1],y=son[p][mark^1],z=father[x];
    if(y!=0)  father[y]=x;
    if(x==son[z][0])  son[z][0]=p;
    if(x==son[z][1])  son[z][1]=p;
    son[p][mark^1]=x,father[p]=z,son[x][mark]=y,father[x]=p,update(x);
}
void Splay(int p,int k)
{
    push_down(p);
    while(father[p]!=k)
    {
        int x=father[p],y=father[x];
        push_down(y),push_down(x),push_down(p);
        if(y==k)  Rotate(p,x);
        else if((p==son[x][0])^(x==son[y][0]))  Rotate(p,x),Rotate(p,y);
        else Rotate(x,y),Rotate(p,x);
    }
    update(p);
    if(k==0)  root=p;
}
int Select(int rank,int k)
{
    int p=root;
    push_down(p);
    while(size[son[p][0]]+1!=rank)
    {
        if(size[son[p][0]]+1<rank)  rank=rank-size[son[p][0]]-1,p=son[p][1];
        else p=son[p][0];
        push_down(p);
    }
    Splay(p,k);
    return p;
}
void Swap(int l,int r)
{
    l=Select(l,0),r=Select(r,l);
    update1(son[r][0]),Splay(son[r][0],0);
}
void Invert(int l,int r)
{
    l=Select(l,0),r=Select(r,l);
    update2(son[r][0]),Splay(son[r][0],0);
}
void Replace(int l,int r,char k)
{
    l=Select(l,0),r=Select(r,l);
    update3(son[r][0],k==')'?-1:1),Splay(son[r][0],0);
}
int Query(int l,int r)
{
    l=Select(l,0),r=Select(r,l);
    return (1-minpre[son[r][0]])/2+(maxsub[son[r][0]]+1)/2;
}
void read()
{
    char a[MAXN];
    scanf("%d %d %s",&n,&m,a+2);
    for(int i=2;i<=n+1;i++)
        v[i]=(a[i]=='('?1:-1);
    n+=2;
    root=(1+n)>>1,Build(1,n);
}
void Ask()
{
    char task[10],p[10];
    for(int i=1,l,r;i<=m;i++)
    {
        scanf("%s",task);
        if(strcmp(task,"Replace")==0)
        {
            scanf("%d %d %s",&l,&r,p);
            Replace(l,r+2,p[0]);
        }
        if(strcmp(task,"Swap")==0)
        {
            scanf("%d %d",&l,&r);
            Swap(l,r+2);
        }
        if(strcmp(task,"Invert")==0)
        {
            scanf("%d %d",&l,&r);
            Invert(l,r+2);
        }
        if(strcmp(task,"Query")==0)
        {
            scanf("%d %d",&l,&r);
            printf("%d\n",Query(l,r+2));
        }
    }
}
int main()
{
    read();
    Ask();
    return 0;
}


  评论这张
 
阅读(744)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017