原題鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1754
這一題裸的線段樹區(qū)間最值+單點(diǎn)修改，但有一個巨大的坑……
return max(cnt,query(i/2,j/2)); //超時
改成：
int q=query(i/2,j/2);
return cnt>q?cnt:q; //AC
為什么呢癣猾？因?yàn)閙ax(）竟然是宏定義的（部分編譯器是這樣的）：
#define max(x1, y1) ((x1) > (y1) ? (x1) : (y1))
原來的代碼展開后：
cnt>query(i/2,j/2) ? cnt : query(i/2,j/2);
查詢函數(shù)執(zhí)行了兩次敛劝。。
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);
}
}
}
