1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
|
#include <iostream> #include <stdio.h> #define ll long long #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 using namespace std; const int MAXN = 1e5 + 10; struct tree { int l,r; long long sum; long long Icm; }tree[MAXN<<2];
void push_up(int rt){//向上更新 tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum; }
void push_down(int rt, int m){ if(tree[rt].Icm){//若有标记,则将标记向下移动一层 tree[rt << 1].Icm += tree[rt].Icm; tree[rt << 1 | 1].Icm += tree[rt].Icm; tree[rt << 1].sum += (m - (m >> 1)) * tree[rt].Icm; tree[rt << 1 | 1].sum += (m >> 1) * tree[rt].Icm; tree[rt].Icm = 0;//取消本层标记 } }
void build(int l, int r, int rt){//建树 //cout<<rt<<endl; tree[rt].l=l; tree[rt].r=r; tree[rt].Icm = 0; if(l == r){ scanf("%lld", &tree[rt].sum); return; } int mid = (l + r) >> 1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); push_up(rt);//向上更新 }
void update(int L, int R, ll key,int rt){//区间更新 if(L == tree[rt].l && R == tree[rt].r){ tree[rt].sum += (tree[rt].r - tree[rt].l + 1) * key; tree[rt].Icm += key; return; } push_down(rt, tree[rt].r - tree[rt].l + 1);//向下更新 int mid = (tree[rt].l + tree[rt].r) >> 1; if(R <= mid) update(L, R, key,rt<<1); else if(L > mid) update(L, R, key,rt<<1|1); else { update(L,mid,key,rt<<1); update(mid+1,R,key,rt<<1|1); } push_up(rt);//向上更新 }
ll query(int L, int R, int rt){//区间求和 //cout<<rt<<' '<<tree[rt].l<<' '<<tree[rt].r<<endl;; if(L == tree[rt].l && tree[rt].r == R) return tree[rt].sum; push_down(rt, tree[rt].r - tree[rt].l + 1);//向下更新 int mid = (tree[rt].l + tree[rt].r) >> 1; ll ans = 0; if(R <= mid) ans += query(L, R, rt<<1); else if(L > mid) ans += query(L, R, rt<<1|1); else { ans+=query(L,mid,rt<<1)+query(mid+1,R,rt<<1|1); } return ans; }
int main(void){ int n, m; scanf("%d%d", &n, &m); build(1, n, 1); while(m--){ char str[3]; int x, y; ll z; scanf("%s", str); if(str[0] == 'C'){ scanf("%d%d%lld", &x, &y, &z); update(x, y, z, 1); }else{ scanf("%d%d", &x, &y); printf("%lldn", query(x, y, 1)); } } }
|
近期评论