首页 > ACM题库 > HDU-杭电 > HDU 1754 I Hate It-线段树-[解题报告] C++
2013
12-21

HDU 1754 I Hate It-线段树-[解题报告] C++

I Hate It

问题描述 :

很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。

输入:

本题目包含多组测试,请处理到文件结束。
在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取’Q'或’U') ,和两个正整数A,B。
当C为’Q'的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。
当C为’U'的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。

输出:

对于每一次询问操作,在一行里面输出最高成绩。

样例输入:

5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

样例输出:

5
6
5
9

Hint
Huge input,the C function scanf() will work better than cin

线段树的问题,不知道为什么我的代码老是runtime error ,哪位大牛能告诉我啊

#include <stdio.h>

int max(int d,int b)//这里如果用inline会加速好多啊
{
    return d>b?d:b;
}


#define  MAXN  2000000
int a[MAXN+5];


struct node
{
    int left;
    int right;
    int sum;
} b[MAXN*2];


void build(int left , int right , int i)//为left,right ,sum赋值
{
    int mid;
    b[i].left=left;
    b[i].right=right;
    if(left==right)
    {
        b[i].sum=a[left];
        return ;
    }

    mid=(left+right)/2;
    build(left,mid,2*i);
    build(mid+1,right,2*i+1);
    b[i].sum=max(b[2*i].sum , b[2*i+1].sum);

}

void  Update(int id,int value,int i)
{
    if(b[i].left==b[i].right)
    {
        b[i].sum=value;
        return ;
    }


        int mid =(b[i].left+b[i].right)/2;
        if(mid>=id) Update(id,value,2*i);
        if(id>mid) Update(id ,value,2*i+1);
        b[i].sum=max(b[i*2].sum , b[2*i+1].sum);//注意更新的时候不仅更新子节点,还要更新父节点

}


int Query(int left, int right,int i)
{
    int mid;
    if(b[i].left==left && b[i].right ==right) return b[i].sum;
    mid=(b[i].left+b[i].right)/2;
    if(right<=mid) return Query(left,right,2*i);
    if (left>mid ) return Query(left,right,2*i+1);
    if(left<=mid && mid<right)
    return max(Query(left,mid,2*i) , Query(mid+1,right,2*i+1));
}


int main()
{
    int n,m;
    char c;
    int id,value;
    int i;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        //scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        build(1,n,1);
        for(i=0;i<m;i++)
        {
            scanf("%c",&c);
            scanf("%d%d",&id,&value);
            if(c=='U') Update(id,value,1);
            if(c=='Q') printf("%d\n",Query(id,value,1));
        }
    }
    return 0;
}
终于知道哪错了,有两个地方,第一b[]数组开小了,至少要三倍或者四倍a[]数组,第二输入char c时有误,要用char c[3],要输入一个字符串,因为单独输入一个字符的话会把回车给独到
char c 中,在最下面贴最新的代码

另外附一个能A的

#include <iostream>
 #include <cstdio>
 using namespace std;
  
 const int MAXN=2000000;
  
 int n,m,a[MAXN+5];
  
 struct tree
 {
     int l,r;
  
     int v;
  
 }trees[MAXN*2];
  
 int max(int k,int l)
 {
     return k>l?k:l;
 }
  
 void buildtree(int rs,int l,int r)
 {
     //printf("%d %d %d\n",rs,l,r);
     trees[rs].l=l;
     trees[rs].r=r;
     if(r==l)
     {
         trees[rs].v=a[l];
         return ;
     }
  
     int mid=(l+r)/2;
  
     buildtree(rs*2,l,mid);
     buildtree(rs*2+1,mid+1,r);
  
     trees[rs].v=max(trees[rs*2].v,trees[rs*2+1].v);
 }
  
 void update(int rs,int k,int l)
 {
     //printf("%d %d %d %d %d\n",rs,k,l,trees[rs].l,trees[rs].r);
  
     if(trees[rs].l==k&&trees[rs].r==k)
     {
         trees[rs].v=l;
         return ;
     }
  
     int mid=(trees[rs].l+trees[rs].r)/2;
  
     if(k<=mid)update(rs*2,k,l);
     if(k>mid)update(rs*2+1,k,l);
      
     trees[rs].v=max(trees[rs*2].v,trees[rs*2+1].v);
 }
  
 int querry(int rs,int l,int r)
 {
     //printf("%d %d %d\n",rs,l,r);
     if(trees[rs].l==l&&trees[rs].r==r)
         return trees[rs].v;
  
     int mid=(trees[rs].l+trees[rs].r)/2;
  
     if(r<=mid)return querry(rs*2,l,r);
     if(l>mid)return querry(rs*2+1,l,r);
     if(l<=mid&&r>mid)
         return max(querry(rs*2,l,mid),querry(rs*2+1,mid+1,r));
  
     return 0;
 }
  
 int main()
 {
     int i,ac,bc;
  
     char c;
  
     while(scanf("%d%d",&n,&m)!=EOF)
     {
         for(i=1;i<=n;i++)
             scanf("%d",&a[i]);
  
         buildtree(1,1,n);
  
         for(i=1;i<=m;i++)
         {
             getchar();
  
             scanf("%c%d%d",&c,&ac,&bc);
  
             if(c=='Q')
                 printf("%d\n",querry(1,ac,bc));
             else
                 update(1,ac,bc);
         }
     }
  
     return 0;
 }

解题报告转自:http://www.cnblogs.com/devil-91/archive/2012/08/02/2619316.html


  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯