题目翻译
你有 N 个整数,A1, A2, … , AN。 您需要处理两种 *** 作。
一种类型的 *** 作是将某个给定的数字添加到给定间隔中的每个数字。
另一种是要求给定区间内的数字总和。
题目分析
线段树模板题(同洛谷P3372)
https://www.luogu.com.cn/problem/P3372
代码
#includeusing namespace std; const int MAXN=100005; long long a[MAXN]; long long lazy[MAXN<<2]; struct tree { int l; int r; long long sum; int maxx; int mid() { return (l + r) >> 1; } }; tree node[MAXN<<2]; void pushup(int i) { node[i].sum = node[i << 1].sum + node[i << 1| 1].sum; } void build(int l, int r,int i) { node[i].l = l; node[i].r = r; lazy[i] = 0; if (l == r) { node[i].sum = a[l];; return; } int m = node[i].mid(); build(l, m,i << 1); build( m + 1, r, (i << 1 | 1)); pushup(i); } void pushdown(int i, int m) { if (lazy[i]) { lazy[i << 1] += lazy[i]; lazy[i << 1 | 1] += lazy[i]; node[i << 1].sum += lazy[i] * (m - (m >> 1)); node[i << 1 | 1].sum += lazy[i] * (m >> 1); lazy[i] = 0; } } void update(long long c,int l,int r,int i) { if (node[i].l ==l&& node[i].r==r) { lazy[i] += c; node[i].sum += c * (r - l + 1); return; } if (node[i].l == node[i].r)return; int m = node[i].mid(); pushdown(i, node[i].r - node[i].l + 1); if (r <= m)update(c, l, r, i << 1); else if (l > m)update(c, l, r, i << 1|1); else { update(c, l, m, i << 1); update(c, m+1, r, i << 1 | 1); } pushup(i); } long long query(int l, int r, int i) { if (node[i].l == l && node[i].r == r) { return node[i].sum; } int m = node[i].mid(); pushdown(i, node[i].r - node[i].l + 1); long long res = 0; if (r <= m)res+=query(l, r, i << 1); else if (l > m)res+=query(l, r, i << 1|1); else { res+=query(l, m, i << 1); res+=query(m+1, r, i << 1 | 1); } return res; } int main() { int p,q,m,n; char t; long long c; cin >> p >> q; for (int k = 1; k <= p; k++) scanf("%lld", &a[k]); build(1, p, 1); while (q--) { cin >> t; if (t == 'Q') { scanf("%d %d", &m, &n); printf("%lldn",query(m, n, 1)); } if (t == 'C') { scanf("%d %d %lld", &m, &n, &c); update(c, m, n, 1); } } return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)