线段树(成段更新) POJ 3468 A Simple Problem with Integers-白红宇

线段树(成段更新) POJ 3468 A Simple Problem with Integers

阅读量：6050 次

发布时间：2019-06-20

本文共 2638 字，大约阅读时间需要 8 分钟。

1 /*  2     线段树-成段更新：裸题，成段增减，区间求和  3     注意：开long long:)  4 */  5 #include 
     
        6 #include 
      
         7 #include 
       
          8 #include 
        
           9 #include 
         
           10 using namespace std; 11  12 #define lson l, mid, rt << 1 13 #define rson mid + 1, r, rt << 1 | 1 14 #define LL long long 15  16 const int MAXN = 1e5 + 10; 17 const int INF = 0x3f3f3f3f; 18 struct Node 19 { 20     LL sum, add; 21 }node[MAXN << 2]; 22  23 void push_up(int rt) 24 { 25     node[rt].sum = node[rt<<1].sum + node[rt<<1|1].sum; 26 } 27  28 void push_down(int rt, int c) 29 { 30     if (node[rt].add) 31     { 32         node[rt<<1].add += node[rt].add; 33         node[rt<<1|1].add += node[rt].add; 34         node[rt<<1].sum += node[rt].add * (c - (c >> 1)); 35         node[rt<<1|1].sum += node[rt].add * (c >> 1); 36         node[rt].add = 0; 37     } 38 } 39  40 void build(int l, int r, int rt) 41 { 42     node[rt].add = 0; 43     if (l == r)    {scanf ("%I64d", &node[rt].sum);    return ;} 44     int mid = (l + r) >> 1; 45     build (lson);    build (rson); 46  47     push_up (rt); 48 } 49  50 void updata(int ql, int qr, int c, int l, int r, int rt) 51 { 52     if (ql <= l && r <= qr)    {node[rt].sum += (LL) c * (r - l + 1);    node[rt].add += c;    return ;} 53  54     push_down (rt, r - l + 1); 55  56     int mid = (l + r) >> 1; 57     if (ql <= mid)    updata (ql, qr, c, lson); 58     if (qr > mid)    updata (ql, qr, c, rson); 59  60     push_up (rt); 61 } 62  63 LL query(int ql, int qr, int l, int r, int rt) 64 { 65     if (ql <= l && r <= qr)    return node[rt].sum; 66  67     push_down (rt, r - l + 1); 68  69     int mid = (l + r) >> 1;        LL ans = 0; 70     if (ql <= mid)    ans += query (ql, qr, lson); 71     if (qr > mid)    ans += query (ql, qr, rson); 72  73     return ans; 74 } 75  76 int main(void)        //POJ 3468 A Simple Problem with Integers 77 { 78     //freopen ("POJ_3468.in", "r", stdin); 79  80     int n, q; 81     while (scanf ("%d%d", &n, &q) == 2) 82     { 83         build (1, n, 1); 84         while (q--) 85         { 86             char s[3];    int ql, qr, c; 87             scanf ("%s", &s); 88             if (s[0] == 'Q') 89             { 90                 scanf ("%d%d", &ql, &qr); 91                 printf ("%I64d\n", query (ql, qr, 1, n, 1)); 92             } 93             else 94             { 95                 scanf ("%d%d%d", &ql, &qr, &c); 96                 updata (ql, qr, c, 1, n, 1); 97             } 98         } 99     }100 101     return 0;102 }