hdu1754 I Hate It ——线段数入门题

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

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#define maxn 200000<<2
//#define max(a,b) ((a)>(b)?(a):(b))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int Max[maxn];
using namespace std;
void pushup(int rt)
{ Max[rt] = max(Max[rt<<1],Max[rt<<1|1]); }
void build(int l, int r, int rt)
{
    if(l==r) {scanf("%d", &Max[rt]); return;}
    int m=l+((r-l)>>1);
    build(lson);build(rson);
    pushup(rt);
}
void update(int p, int ck, int l, int r, int rt)
{
    if (l==r) {Max[rt] = ck; return;}
    int m=l+((r-l)>>1);
    if (p <= m) update(p, ck, lson);
    else update(p, ck, rson);
    pushup(rt);
}
int query(int L, int R, int l, int r, int rt)
{
    if (L <= l && R >= r) {return Max[rt];}
    int m=l+((r-l)>>1);
    int ret = 0;
    if (L<=m) ret = max(query(L,R,lson),ret);
    if (R>m) ret = max(query(L,R,rson),ret);
    return ret;
}
int main(void)
{
    int N, M;
#ifndef ONLINE_JUDGE
    freopen("in.cpp","r",stdin);
#endif
    while (scanf("%d%d", &N, &M) != EOF)
    {
        build(1,N,1);
        while (M--)
        {
            char c[3];int A,B;
            scanf("%s%d%d", c,&A,&B);
            if (c[0]=='U') update(A,B,1,N,1);
            else printf("%d\n", query(A,B,1,N,1));
        }
    }
    return 0;
}

#include #include #include #include #define maxn 200000<<2 //#define max(a,b) ((a)>(b)?(a):(b)) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int Max[maxn]; using namespace std; void pushup(int rt) { Max[rt] = max(Max[rt<<1],Max[rt<<1|1]); } void build(int l, int r, int rt) { if(l==r) {scanf("%d", &Max[rt]); return;} int m=l+((r-l)>>1); build(lson);build(rson); pushup(rt); } void update(int p, int ck, int l, int r, int rt) { if (l==r) {Max[rt] = ck; return;} int m=l+((r-l)>>1); if (p <= m) update(p, ck, lson); else update(p, ck, rson); pushup(rt); } int query(int L, int R, int l, int r, int rt) { if (L <= l && R >= r) {return Max[rt];} int m=l+((r-l)>>1); int ret = 0; if (L<=m) ret = max(query(L,R,lson),ret); if (R>m) ret = max(query(L,R,rson),ret); return ret; } int main(void) { int N, M; #ifndef ONLINE_JUDGE freopen(“in.cpp”,“r”,stdin); #endif while (scanf(“%d%d”, &N, &M) != EOF) { build(1,N,1); while (M–) { char c[3];int A,B; scanf(“%s%d%d”, c,&A,&B); if (c[0]==‘U’) update(A,B,1,N,1); else printf(“%d\n”, query(A,B,1,N,1)); } } return 0; } ```

发现一个很神奇的东西：库函数中的 max() 比自己定义的效率要高，自己写的 #define max(a,b) ((a)>(b)?(a):(b)) 就会超时。

如果自己写一个 max 函数，不会超时，1093ms,但是会比用库函数(1078ms)慢一些。

现在还不知道为什么宏定义为什么会超时。。

第二次学习线段树，很久不做题目，有点儿手生，比如读入字符c的时候，一般要把c定义为字符数组，这样比较方便，如果定义c为字符，读入的时候可能会出现问题……