题目传送门(BZOJ)

题解 :

线段树, 区间加, 区间求和
注意文末提示可能爆int, 我以为保证不爆int所以竟然还 WA 惹

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define ls p << 1#define rs p << 1|1#define ll long longusing namespace std;const int N = 100010;ll t[N<<2], laz[N<<2];int a[N];void build(int l, int r, int p) { if(l == r) return t[p] = a[l], void(); int mid = (l+r) >> 1; build(l, mid, ls); build(mid+1, r, rs); t[p] = t[ls]+t[rs];}inline void pd(int l, int r, int p) { if(laz[p]) { int mid = (l+r) >> 1; laz[ls] += laz[p], laz[rs] += laz[p]; t[ls] += ((ll)mid-l+1)*laz[p]; t[rs] += ((ll)r-mid)*laz[p]; laz[p] = 0; }}ll query(int l, int r, int p, int x, int y) { if(x <= l && y >= r) return t[p]; pd(l, r, p); int mid = (l+r) >> 1; ll ret = 0; if(x <= mid) ret = query(l, mid, ls, x, y); if(y > mid) ret += query(mid+1, r, rs, x, y); return ret;}void change(int l, int r, int p, int x, int y, int c) { if(x <= l && y >= r) { t[p] += ((ll)r-l+1)*c; laz[p] += c; return ; } pd(l, r, p); int mid = (l+r) >> 1; if(x <= mid) change(l, mid, ls, x, y, c); if(y > mid) change(mid+1, r, rs, x, y, c); t[p] = t[ls]+t[rs];}int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); build(1, n, 1); for(int i = 1; i <= m; i ++ ) { int x, y, c; char opt[3]; scanf("%s%d%d", opt, &x, &y); if(opt[0] == 'Q') { printf("%lld\n", query(1, n, 1, x, y)); } else { scanf("%d", &c); change(1, n, 1, x, y, c); } }}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<