首页 > 代码库 > poj 3468 A Simple Problem with Integers （线段树 成段更新 加值 求和）

poj 3468 A Simple Problem with Integers （线段树 成段更新 加值 求和）

2024-07-16 06:00:34   230人阅读

题目链接

题意：

只有这两种操作

C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.

分析：自己写的有点麻烦了，写的时候手残+脑残，改了好久。

val+lazy*(r-l+1)表示和，如果lazy==0表示当前区间加的值不统一。

  1 #include <iostream>  2 #include <cstdio>  3 #include <vector>  4 #include <cstring>  5 #include <cstdlib>  6 #include <algorithm>  7 #define LL __int64  8 const int maxn = 100000+10;  9 using namespace std; 10 int n, q; 11 __int64 a[maxn]; 12 struct line 13 { 14     int l, r; 15     LL val, lazy; 16 }tr[4*maxn]; 17  18 void build(int o, int l, int r) 19 { 20     tr[o].l = l; tr[o].r = r; 21     tr[o].lazy = 0; 22     if(l==r) 23     { 24         tr[o].val = a[l]; 25         return; 26     } 27     int mid = (l+r)/2; 28     build(2*o, l, mid); 29     build(2*o+1, mid+1, r); 30     tr[o].val = tr[2*o].val+tr[2*o+1].val; 31 } 32 void update(int o, int l, int r, int add) 33 { 34     if(tr[o].l==l && tr[o].r==r) 35     { 36         tr[o].lazy += add; 37         return; 38     } 39     if(tr[o].lazy)  //之前没向下更新的向下更新 40     { 41         tr[2*o].lazy += tr[o].lazy; 42         tr[2*o+1].lazy += tr[o].lazy; 43         tr[o].val += (LL)(tr[o].lazy*(tr[o].r-tr[o].l+1));  //同时把lazy存的加到和里 44         tr[o].lazy = 0; 45     } 46     tr[o].val += (LL)(add*(r-l+1)); //在这个过程中把新增加的加上，注意左右区间 47     int mid = (tr[o].l+tr[o].r)/2; 48     if(r <= mid) update(2*o, l, r, add); 49     else if(l > mid) update(2*o+1, l, r, add); 50     else 51     { 52         update(2*o, l, mid, add); 53         update(2*o+1, mid+1, r, add); 54     } 55 } 56  57 LL query(int o, int l, int r) 58 { 59     if(tr[o].l==l && tr[o].r==r) 60     return tr[o].val + tr[o].lazy*(r-l+1); 61     if(tr[o].lazy)  //由于之前可能存在 没有更新的所以向下更新 62     { 63         tr[2*o].lazy += tr[o].lazy; 64         tr[2*o+1].lazy += tr[o].lazy; 65         tr[o].val += (LL)(tr[o].lazy*(tr[o].r-tr[o].l+1)); 66         tr[o].lazy = 0; 67     } 68     int mid = (tr[o].l+tr[o].r)/2; 69     if(r<=mid) return query(2*o, l, r); 70     else if(l > mid) return query(2*o+1, l, r); 71     else 72     { 73        return query(2*o, l, mid) + query(2*o+1, mid+1, r); 74     } 75 } 76 int main() 77 { 78     int i, l, r, add; 79      char ch; 80     while(~scanf("%d%d", &n, &q)) 81     { 82         for(i = 1; i <= n; i++) 83         scanf("%I64d", &a[i]); 84         build(1, 1, n); 85         for(i = 1; i <= q; i++) 86         { 87             getchar(); 88             scanf("%c", &ch); 89             if(ch==‘Q‘) 90             { 91                 scanf("%d%d", &l, &r); 92                 printf("%I64d\n", query(1, l, r)); 93             } 94             else 95             { 96                 scanf("%d%d%d", &l, &r, &add); 97                 update(1, l, r, add); 98             } 99         }100     }101     return 0;102 }

 


联系
我们