宏用的时候要想清楚！（宏不是那么好用的）

#define MAX(x,y) x>y?x:y

 

从昨天晚上到今天晚上，一直在调试一道线段树求最值的简单题，就是hdu的1754，一直TLE，无语，如此简单的题怎么会这样。搜索别人的代码，发现思路都一样，怎么会这样。

晚上重新写了一遍，结果AC了。然后就找原因，唯一不同的是一个用了

 

另一个AC的用了

 

int max(int x, int y)

{

      return x > y ? x : y;

}

 这下当我调用MAX对query的结果进行取最值的时候就出现了问题。重复计算了一次，导致了致命的超时！。

作为证据贴下自己的两个代码：

//超时的代码：
#include <stdio.h>
#define N 200010
#define MAX(x,y)  x>y?x:y
typedef struct{
    int left, right, mid;
    int score;   
}SegNode;
SegNode a[4 * N + 1];
int p[N + 1];

void build(int left, int right, int ind)
{
    int mid, tl, tr;
    a[ind].left = left;
    a[ind].right = right;
    
    if(left == right) 
    {
        a[ind].score = p[left];
        return ;
    }
    a[ind].mid = (left + right) / 2;
    build(left, a[ind].mid, ind * 2);
    build(a[ind].mid +1, right, ind * 2 + 1);
    a[ind].score = MAX( a[ind * 2].score, a[ind * 2 + 1].score ); // sum of the num 
}

int query(int left, int right, int ind)
{
    if(a[ind].left == left && right == a[ind].right)
        return a[ind].score;
    if(right <= a[ind].mid)
        return query(left, right, ind * 2);
    else if(left > a[ind].mid)
        return query(left, right, ind * 2 + 1);
    else
        return MAX(query(left, a[ind].mid, ind * 2) , query(a[ind].mid +1, right, ind * 2  + 1));
}

void modify(int site, int var, int ind)
{
    if(a[ind].left == a[ind].right)
    {
        a[ind].score = var;
        return;
    }
    if(site <= a[ind].mid)
        modify(site, var, ind * 2);
    else
        modify(site, var, ind * 2 + 1);
    a[ind].score = MAX(a[ind * 2].score , a[ind * 2 + 1].score);
}


int main()
{
    int t;
    int n;
    int i, j, k;
    int st, ed;
    char cmd[10];

        while(scanf("%d%d", &n, &k) == 2)
        {
            for(i = 1; i <= n; i++)
            {
                scanf("%d", &p[i]);    
            }    
            build(1, n, 1);
        
            while(k--)
            {
                getchar();
                scanf("%c%d%d", &cmd[0], &st, &ed);
                if(cmd[0] == 'Q')
                    printf("%d\n", query(st, ed, 1));
                else
                    modify(st, ed, 1);                                        
            }
        }
    return 0;    
}

 

//AC的代码：
#include <stdio.h>
#define N 200010

typedef struct{
    int l, r, mid;
    int mmax;
}NODE;

static inline int  MAX(int x, int y)
{
    return x>y?x:y;    
}

NODE node[N * 4 + 1];
int val[N];
void build_tree(int ll, int rr, int ind)
{
    node[ind].l = ll;
    node[ind].r = rr;
    if(ll == rr)
    {
            node[ind].mmax = val[ll];
            return ;
    }    
    node[ind].mid = (ll + rr) / 2;
    build_tree(ll, node[ind].mid, ind * 2);
    build_tree(node[ind].mid + 1 , rr, ind * 2 + 1);
    node[ind].mmax = MAX(node[ind * 2].mmax, node[ind * 2 + 1 ].mmax);    
}

int query(int ll, int rr, int ind)
{
   if(ll == node[ind].l && rr == node[ind].r)
        return node[ind].mmax;
   
   if(rr <= node[ind].mid) 
        return query(ll, rr, ind * 2);
   if(ll > node[ind].mid)
        return query(ll, rr, ind * 2 + 1);
    return MAX(query(ll, node[ind].mid, ind * 2), query(node[ind].mid + 1, rr, ind * 2 + 1));
}

void update(int site, int b, int ind)
{
    if(node[ind].l == node[ind].r)
    {
            node[ind].mmax = b;
            return ;
    }
    if(site <= node[ind].mid)
        update(site, b, ind * 2);
    else 
        update(site, b, ind * 2 + 1); 
    node[ind].mmax = MAX(node[ind * 2].mmax, node[ind * 2 + 1].mmax);   
}

int main()
{
    int n, k;
    int i;
    int a, b;
    char c;
    while(scanf("%d%d", &n, &k) != EOF)
    {
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &val[i]);    
        } 
        //printf("yes\n");   
        build_tree(1, n, 1);
        //printf("over\n");
        while(k--)
        {
            getchar();
            scanf("%c%d%d", &c, &a, &b);
            //printf("%c %d %d\n", c, a, b);
            if(c == 'Q')
                printf("%d\n", query(a, b, 1));
            else
                update(a, b, 1);    
        }
    }
    return 0;    
}