【HDU 1754】震惊！max()传入耗时函数导致超时。

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1754

这一题裸的线段树区间最值+单点修改，但有一个巨大的坑……

return max(cnt,query(i/2,j/2));         //超时

改成：
int q=query(i/2,j/2);
return cnt>q?cnt:q;                    //AC

为什么呢？因为max(）竟然是宏定义的（部分编译器是这样的）：

#define max(x1, y1) ((x1) > (y1) ? (x1) : (y1))

原来的代码展开后：

 cnt>query(i/2,j/2) ? cnt : query(i/2,j/2);

查询函数执行了两次。。

ac代码：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm> 
using namespace std;
int tree[200000*4];

void updata(int i,int num){
    tree[i]=num;
    i/=2;
    while(i>=1){
        tree[i]=tree[i*2]>tree[i*2+1]?tree[i*2]:tree[i*2+1];
        i/=2;
    }
}

int query(int i,int j){
    if (j-i==1) return max(tree[i],tree[j]);
    if (j==i) return tree[i];
    int cnt=0;
    if (i%2!=0){
        cnt=tree[i];
        i++;
    }
    if (j%2==0){
        if (cnt<tree[j]) cnt=tree[j];
        j--;
    }
    int q=query(i/2,j/2);
    return cnt>q?cnt:q;
}   

int main()
{
    int n,m,N,a,x,y;
    char c;
    while(~scanf("%d%d",&n,&m)){
        memset(tree,0,sizeof(tree));
        N=1;
        while(N<n) N*=2;
        for (int i=1;i<=n;++i){
            scanf("%d",&a);
            updata(N-1+i,a);
        }
        while(m--){
            getchar();
            scanf("%c %d %d",&c,&x,&y);
            if (c=='Q') printf("%d\n",query(N-1+x,N-1+y));
            else if (c=='U') updata(N-1+x,y);
        }
    }
}