付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0
线段树的入门题 用来查询区间的最大最小值

是用模板过的 不过也是在看懂之后 才会用
#include <stdio.h>

#define N 200000+1
struct Node
{
    
int l,r;
    
int max;
}seg[
3*N];
int num[N];
int ans;
int Max(int a,int b)
{
    
return a>b?a:b;
}

void build(int l,int r,int k)
{
    seg[k].l
=l;
    seg[k].r
=r;
    
    
if(l==r)
    {
        seg[k].max 
= num[l];
        
return ;
    }
    
else
    {
        
int mid = (l+r)/2;
        build(l,mid,
2*k);
        build(mid
+1,r,2*k+1);
        seg[k].max 
= Max(seg[2*k].max,seg[2*k+1].max);
    }
    
return ;
}

void Search(int l,int r,int k)
{
    
if(seg[k].l==&& seg[k].r==r)
    {
        
if(seg[k].max>ans)
            ans 
= seg[k].max;
        
return ;
    }
    
else
    {
        
int mid=(seg[k].l+seg[k].r)/2;
        
if(mid>=r)
            Search(l,r,
2*k);
        
else if(mid<l)
            Search(l,r,
2*k+1);
        
else
        {
            Search(l,mid,
2*k);
            Search(mid
+1,r,2*k+1);
        }

    }
}
void Update(int l,int r,int value,int k)
{
    
if(seg[k].l== l && seg[k].r==r)
    {
        seg[k].max 
= value;
        
return ;
    }
    
else
    {
        
int mid = (seg[k].l+seg[k].r)/2;
        
if(mid>=r)
            Update(l,r,value,
2*k);
        
else if(mid<l)
            Update(l,r,value,
2*k+1);
        
else
        {
            Update(l,mid,value,
2*k);
            Update(mid
+1,r,value,2*k+1);
        }
        seg[k].max 
= Max(seg[2*k].max,seg[2*k+1].max);
    }
    
return ;
}
int main()
{
    
char ch;
    
int a,b,m,n,i;
    
    
while(scanf("%d%d",&m,&n)!=EOF)
    {
        
for(i=1;i<=m;i++)
            scanf(
"%d",num+i);
        build(
1,m,1);
        
for(i=0;i<n;i++)
        {
            getchar();
            ch 
= getchar();
            
if(ch=='Q')
            {
                scanf(
"%d%d",&a,&b);
                ans 
= 0;
                Search(a,b,
1);
                printf(
"%d\n",ans);
            }
            
else if(ch=='U')
            {
                scanf(
"%d%d",&a,&b);
                Update(a,a,b,
1);
            }
        }
    }
    
return 0;
}


posted on 2010-05-13 16:08 付翔 阅读(98) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构

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



<2010年5月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜