题目中文的，不解释了

维护一个最大值的线段树

1 #include 
     
       2  3 #define lson l, m, rt<<1 4 #define rson m+1, r, rt<<1|1 5  6 const int maxn = 200000; 7  8 char cmd[2]; 9 int  n, mNum, a, b, max[maxn<<2];10 11 int Max(int x, int y)12 {13     return (x>y ? x:y);14 }/* Max */15 16 void BuildTree(int l, int r, int rt)17 {18     if (l == r)19     {20         scanf("%d", &max[rt]);21         return ;22     }/* End of If */23     24     int m = (l+r)>>1;25     BuildTree(lson);26     BuildTree(rson);27     max[rt] = Max(max[rt<<1], max[rt<<1|1]);    /* Push Up */28 }/* BuildTree */29 30 int Query(int L, int R, int l, int r, int rt)31 {32     if (L<=l && r<=R)33         return max[rt];34     35     int ret=-1, m=(l+r)>>1;36 37     if (L <= m)38         ret = Max(ret, Query(L, R, lson));39     if (R > m)40         ret = Max(ret, Query(L, R, rson));41 42     return ret;43 }/* Query */44 45 void UpData(int p, int bi, int l, int r, int rt)46 {47     if (l == r)48     {49         max[rt] = bi;50         return ;51     }/* End of If */52 53     int m = (l+r)>>1;54 55     if (p <= m)56         UpData(p, bi, lson);57     else58         UpData(p, bi, rson);59         60     max[rt] = Max(max[rt<<1], max[rt<<1|1]);    /* Push Up */61 }/* UpData */62 63 int main()64 {65     while (~scanf("%d %d", &n, &mNum))66     {67         BuildTree(1, n, 1);68         for (int i=1; i<=mNum; ++i)69         {70             scanf("%s %d %d", cmd, &a, &b);71             if (cmd[0] == 'Q')  /* Query */72                 printf("%d\n", Query(a, b, 1, n, 1));73             else    /* UpData */74                 UpData(a, b, 1, n, 1);75         }76     }/* End of While */77     78     return 0;79 }