C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

hdu 1754 I Hate It 解题报告

Posted on 2011-11-15 09:26 C小加 阅读(3825) 评论(1)  编辑 收藏 引用 所属分类: 解题报告
第二个线段树,超时了两次, 原因是读数据的时候忘了加上EOF,郁闷。

#include 
<iostream>
#include 
<cstdio>
#include 
<cstring>
using namespace std;
const int MAXN=200003;
const int INF=0x7fffffff-1;
int v[MAXN],sum;
typedef 
struct
{
    
int left,right,mid;
    
int count;
}line;
line l[
4*MAXN];
void Creat(int a,int b,int r)
{
    
if(a==b)
    {
        l[r].left
=l[r].right=a;
        l[r].count
=v[a];
        
return;
    }
    l[r].left
=a;
    l[r].right
=b;
    l[r].mid
=(a+b)>>1;
    Creat(a,l[r].mid,r
<<1);
    Creat(l[r].mid
+1,b,(r<<1)+1);
    l[r].count
=max(l[r<<1].count,l[(r<<1)+1].count);
}
void Add(int n,int m,int r)
{
    
if(l[r].left==n&&l[r].right==n)
    {
        l[r].count
=m;
        
return;
    }
    
if(n>l[r].mid)
    {
        Add(n,m,(r
<<1)+1);
    }
    
else
    {
        Add(n,m,r
<<1);
    }
    l[r].count
=max(l[r<<1].count,l[(r<<1)+1].count);
}
int Query(int a,int b,int r)
{
    
if(l[r].left==a&&l[r].right==b)
    {
        
return l[r].count;

    }
    
else if(a>l[r].mid)
    {
        
return Query(a,b,2*r+1);
    }
    
else if(b<=l[r].mid)
    {
        
return Query(a,b,2*r);
    }
    
else
    {
        
int x=Query(a,l[r].mid,r<<1);
        
int y=Query(l[r].mid+1,b,(r<<1)+1);
        
return max(x,y);
    }
}
int main()
{
    
int n,m;
    
while(scanf("%d %d",&n,&m)!=EOF)
    {
        
for(int i=1;i<=n;i++)
        {
            scanf(
"%d",&v[i]);
        }
        Creat(
1,n,1);
        
char s[2];
        
for(int i=0;i<m;i++)
        {
            scanf(
"%s",s);
            
int b,c;
            scanf(
"%d %d",&b,&c);
            
if(s[0]=='Q')
            {
                printf(
"%d\n",Query(b,c,1));
            }
            
else
            {
                Add(b,c,
1);
            }

        }
    }
    
return 0;
}

Feedback

# re: hdu 1754 I Hate It 解题报告  回复  更多评论   

2011-11-15 16:09 by 安平信息港
支持一个 厉害了 ~

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