題目鏈接：A Simple PRoblem with Integers 題意：n個數，q次操作，操作分為詢問和修改操作，修改是讓[a,b]的元素加上c，查詢是求[a,b]元素的和 解析：線段樹，區間修改，區間查詢
#include <algorithm>#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int maxn = 100000+100;struct node{ int l,r; long long lazy,sum; void update(int val) { sum += 1LL*(r-l+1)*val; lazy+= val; }}tree[4*maxn];int a[maxn];void push_up(int i){ tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;}void push_down(int i){ long long lazyVal = tree[i].lazy; if(lazyVal) { tree[i<<1].update(lazyVal); tree[i<<1|1].update(lazyVal); tree[i].lazy = 0; }}void build(int i,int l,int r){ tree[i].l = l,tree[i].r = r; tree[i].sum = tree[i].lazy = 0; if(l==r) { tree[i].sum = a[r]; return ; } int mid = (l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); push_up(i);}void update(int i,int l,int r,int val){ int L = tree[i].l; int R = tree[i].r; if(l<=L && R<=r) { tree[i].update(val); return ; } push_down(i); int mid = (L+R)>>1; if(mid<r) update(i<<1|1,l,r,val); if(mid>=l) update(i<<1,l,r,val); push_up(i);}long long query(int i,int l,int r){ int L = tree[i].l; int R = tree[i].r; if(l<=L && R<=r) return tree[i].sum; long long ans = 0; push_down(i); int mid = (L+R)>>1; if(mid<r) ans += query(i<<1|1,l,r); if(mid>=l) ans += query(i<<1,l,r); push_up(i); return ans;}int main(void){ int n,q; while(~scanf("%d %d",&n,&q)) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); char op[10]; while(q--) { int x,y; scanf("%s %d %d",op,&x,&y); if(op[0]=='C') { int val; scanf("%d",&val); update(1,x,y,val); } else printf("%I64d/n",query(1,x,y)); } } return 0;}新聞熱點
疑難解答
