The Fourth Dimension Space

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

HDOJ 1698 Just a Hook 线段树

题目的意思是给你一个数组,大小是N,初始的时候,a[1-N]均为1,然后有Q个操作,每次操作修改某个区间中的值,求最后整个区间1-N的和。线段树解决

#include<iostream>
using namespace std;

int const maxn=100100;

struct node
{
    
int n;
    
int l,r;
}
tree[maxn*4];

void build(int l,int r,int i)
{
    tree[i].l
=l;
    tree[i].r
=r;
    
if(l==r)
        
return;

    
int mid=(l+r)>>1;
    build(l,mid,i
*2);
    build(mid
+1,r,i*2+1);
}


void update(int l,int r,int n,int i)
{
    
if(l==tree[i].l&&r==tree[i].r)
    
{
        tree[i].n
=n;
        
return ;
    }

    
if(l>r)
        
return ;
    
int nn=tree[i].n;
    
if(tree[i].n!=0)
    
{
        
if(l!=tree[i].l||r!=tree[i].r)
        
{
            
            
int mid=(tree[i].l+tree[i].r)>>1;
            
if(r<=mid)
            
{
                update(l,r,n,i
*2);
                update(tree[i].l,l
-1,nn,i*2);
                update(r
+1,mid,nn,i*2);
                update(mid
+1,tree[i].r,nn,i*2+1);
            }

            
else if(l>mid)
            
{
                update(l,r,n,i
*2+1);
                update(r
+1,tree[i].r,nn,i*2+1);
                update(mid
+1,l-1,nn,i*2+1);
                update(tree[i].l,mid,nn,i
*2);

            }

            
else
            
{
                update(l,mid,n,i
*2);
                update(mid
+1,r,n,i*2+1);
                update(tree[i].l,l
-1,nn,i*2);
                update(r
+1,tree[i].r,nn,i*2+1);
            }

            
        }

        tree[i].n
=0;
    }


    
else if(tree[i].n==0)
    
{
        
if(l!=tree[i].l||r!=tree[i].r)
        
{
            
int mid=(tree[i].l+tree[i].r)>>1;
            
if(r<=mid)
                update(l,r,n,i
*2);
            
else if(l>mid)
                update(l,r,n,i
*2+1);
            
else
            
{
                update(l,mid,n,i
*2);
                update(mid
+1,r,n,i*2+1);
            }

        }

    }

}



int Que(int l,int r,int i)
{
    
int ans=0;
    
if(tree[i].l==l&&tree[i].r==r&&tree[i].n!=0)
    
{
        ans
=(r-l+1)*tree[i].n;
        
return ans;
    }

    
else
    
{
        
int mid=(tree[i].l+tree[i].r)>>1;
        
if(r<=mid)
            ans
= Que(l,r,i*2);
        
else if(l>mid)
            ans
= Que(l,r,i*2+1);
        
else
             ans
=Que(l,mid,i*2)+Que(mid+1,r,i*2+1);
        
return ans;
    }

}




int main()
{
    
int ca;
    scanf(
"%d",&ca);
    
int t=0;
    
while(ca--)
    
{
        t
++;

        
int n;
        scanf(
"%d",&n);
        build(
1,n,1);
        tree[
1].n=1;
        
int q;
        scanf(
"%d",&q);
        
int i;
        
for(i=1;i<=q;i++)
        
{
            
int a,b,c;
            scanf(
"%d%d%d",&a,&b,&c);
            update(a,b,c,
1);
        }

        printf(
"Case %d: The total value of the hook is %d.\n",t,Que(1,n,1));
    }

    
return 0;
}

发现我现场写线段树的能力太差,以后这种东西一定要能够手写,这题要好好总结一下。恩。东西学的多了,不一定是好事,对于灵活的东西一定要做到非常熟练,否则比赛的时候会很慢的。
#include<iostream>
using namespace std;
int const maxn=100100;

struct node
{
    
int n;
    
int l,r;
}
tree[maxn*4];

void build(int l,int r,int i)
{
    tree[i].l
=l;
    tree[i].r
=r;
    tree[i].n
=1;
    
if(l==r)
        
return;

    
int mid=(l+r)>>1;
    build(l,mid,i
*2);
    build(mid
+1,r,i*2+1);
}


void update(int l,int r,int n,int i)
{
    
int nn=tree[i].n;
    
if(l==tree[i].l&&r==tree[i].r)
    
{
        tree[i].n
=n;
        
return ;
    }

    
if(tree[i].n!=0)
    
{
        tree[i
*2].n=tree[i].n;
        tree[i
*2+1].n=tree[i].n;
        tree[i].n
=0;
    }

    
int mid=(tree[i].l+tree[i].r)>>1;
    
{
        
if(r<=mid)
            update(l,r,n,i
*2);
        
else if(l>mid)
            update(l,r,n,i
*2+1);
        
else
        
{
            update(l,mid,n,i
*2);
            update(mid
+1,r,n,i*2+1);
        }

    }

    
}



int Que(int l,int r,int i)
{
    
int ans=0;
    
if(tree[i].l==l&&tree[i].r==r&&tree[i].n!=0)
    
{
        ans
=(r-l+1)*tree[i].n;
        
return ans;
    }

    
else
    
{
        
int mid=(tree[i].l+tree[i].r)>>1;
        
if(r<=mid)
            ans
= Que(l,r,i*2);
        
else if(l>mid)
            ans
= Que(l,r,i*2+1);
        
else
            ans
=Que(l,mid,i*2)+Que(mid+1,r,i*2+1);
        
return ans;
    }

}




int main()
{
    
int ca;
    scanf(
"%d",&ca);
    
int t=0;
    
while(ca--)
    
{
        t
++;

        
int n;
        scanf(
"%d",&n);
        build(
1,n,1);
        tree[
1].n=1;
        
int q;
        scanf(
"%d",&q);
        
int i;
        
for(i=1;i<=q;i++)
        
{
            
int a,b,c;
            scanf(
"%d%d%d",&a,&b,&c);
            update(a,b,c,
1);
        }

        printf(
"Case %d: The total value of the hook is %d.\n",t,Que(1,n,1));
    }

    
return 0;
}

posted on 2010-07-17 11:42 abilitytao 阅读(178) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理