The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

HDOJ 1540 Tunnel Warfare 线段树

题意:可以标记区间上某些节点或者取消标记,并查询与x连续的未被标记的结点数。
这题和Hotel类似,由于换成了单节点操作,不需要区间操作的延迟标记,维护起来更方便。

#include<iostream>
#include
<algorithm>
using namespace std;
int const maxn=50010;
#define LL(i) (i<<1)
#define RR(i) ((i<<1)+1)

struct node
{

    
int l,r;
    
int lval,rval;
    
int len()
    
{
        
return r-l+1;
    }

}
ST[maxn*4];
int n,m;

void build(int l,int r,int i)
{
    ST[i].l
=l;
    ST[i].r
=r;
    
if(l==r)
    
{
        ST[i].lval
=1;
        ST[i].rval
=1;
        
return;
    }

    
int mid=(l+r)>>1;
    build(l,mid,LL(i));
    build(mid
+1,r,RR(i));
    ST[i].lval
=ST[i].len();
    ST[i].rval
=ST[i].len();
}



void update(int x,int op,int i)
{

    
if(ST[i].l==ST[i].r)
    
{
        
if(op==1)
            ST[i].lval
=ST[i].rval=0;
        
else if(op==0)
            ST[i].lval
=ST[i].rval=1;
        
return;
    }

    
int mid=(ST[i].l+ST[i].r)>>1;
    
if(x<=mid) update(x,op,LL(i));
    
else update(x,op,RR(i));

    ST[i].lval
=ST[LL(i)].lval;
    ST[i].rval
=ST[RR(i)].rval;

    
if(ST[LL(i)].lval==ST[LL(i)].len())
        ST[i].lval
+=ST[RR(i)].lval;
    
if(ST[RR(i)].rval==ST[RR(i)].len())
        ST[i].rval
+=ST[LL(i)].rval;
}



int Query(int x,int i)
{
    
if(ST[i].l==ST[i].r)
        
return ST[i].lval;
    
int mid=(ST[i].l+ST[i].r)>>1;
    
if(x<=mid)
    
{
        
if(x<=ST[i].lval)
            
return ST[i].lval;
        
if(x>=ST[LL(i)].r-ST[LL(i)].rval+1)
            
return ST[LL(i)].rval+ST[RR(i)].lval;
        
else return Query(x,LL(i));
    }

    
else
    
{
        
if(x>=ST[i].r-ST[i].rval+1)
            
return ST[i].rval;
        
if(x<=ST[RR(i)].l+ST[RR(i)].lval-1)
            
return ST[RR(i)].lval+ST[LL(i)].rval;
        
else return Query(x,RR(i));
    }

}



int d[maxn];
int pd=0;

int main()
{
    
while(scanf("%d%d",&n,&m)!=EOF)
    
{
        build(
1,n,1);
        
char op[100];
        
int x;
        pd
=0;
        
for(int i=0;i<m;i++)
        
{

            scanf(
"%s",op);
            
if(op[0]=='D')
            
{
                scanf(
"%d",&x);
                update(x,
1,1);
                d[pd
++]=x;
            }

            
else if(op[0]=='Q')
            
{

                scanf(
"%d",&x);
                printf(
"%d\n",Query(x,1));
            }

            
else
            
{
                update(d[
--pd],0,1);
            }

        }

    }

    
    
return 0;
}

posted on 2010-10-30 10:34 abilitytao 阅读(1227) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理