- 题目大意
有两种命令,Q是查询一个区间的和,C是一个区间同时增加一个数。
- 解题思路
主要是线段树的点的更新和存储问题。每个一个数都更新到叶子节点不是明智的做法,很消耗时间。故每个节点加一个特殊量来记录增量的累加。
- 代码
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstring> #include<stack> using namespace std; const int maxn = 100001; int num[maxn]; struct node { int l, r; long long a,s; }t[4 * maxn]; long long ans; void build(int l, int r, int k) { int mid; t[k].l = l; t[k].r = r; t[k].a=0; if (l == r) return; mid = (l + r) / 2; build(l, mid, 2 * k); build(mid + 1, r, 2 * k + 1); t[k].s=t[k*2].s+t[k*2+1].s; } void add(int l, int r, int x,int i) { int mid; if(t[i].l>r||t[i].r<l) return; mid = (t[i].r + t[i].l) / 2; if (t[i].l>=l&&t[i].r<=r) { t[i].s+=(t[i].r-t[i].l+1)*x; t[i].a+=x; return; } if(t[i].a) { t[i*2].s+=(t[i*2].r-t[i*2].l+1)*t[i].a; t[i*2].a+=t[i].a; t[i*2+1].s+=(t[i*2+1].r-t[i*2+1].l+1)*t[i].a; t[i*2+1].a+=t[i].a; t[i].a=0; } add(l,r,x,i*2); add(l,r,x,i*2+1); t[i].s=t[i*2].s+t[i*2+1].s; } void findd(int l,int r, int i) { int mid; if(t[i].l>r||t[i].r<l) return; if(t[i].l>=l&&t[i].r<=r) { ans+=t[i].s; return; } if(t[i].a) { t[i*2].s+=(t[i*2].r-t[i*2].l+1)*t[i].a; t[i*2].a+=t[i].a; t[i*2+1].s+=(t[i*2+1].r-t[i*2+1].l+1)*t[i].a; t[i*2+1].a+=t[i].a; t[i].a=0; } findd(l,r,i*2); findd(l,r,i*2+1); t[i].s=t[i*2].s+t[i*2+1].s; } int main() { int n, m, a,b,c; char str[2]; scanf("%d%d", &n, &m); for(int i=1;i<=n;i++) scanf("%d",&num[i]); build(1, n, 1); for(int i=1;i<=n;i++) add(i,i,num[i],1); while(m--) { scanf("%s",&str); if(str[0]=='C') { scanf("%d%d%d",&a,&b,&c); add(a,b,c,1); } if(str[0]=='Q') { ans=0; scanf("%d%d",&a,&b); findd(a,b,1); printf("%lld ",ans); } } return 0; }