hdoj1754 线段树--单点更新

Myth丶恋晨 2021-11-04 12:20 332阅读 0赞

题目中文的，不解释了

维护一个最大值的线段树

1 #include <stdio.h>
     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     else
    58         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 }

转载于:https://www.cnblogs.com/yewei/archive/2012/05/03/2480675.html