AcWing243. 一个简单的整数问题2
给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。
2、“Q l r”，表示询问 数列中第 l~r 个数的和。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行表示M条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<cmath> #include<algorithm> #include<vector> #include<utility> #include<deque> #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define fi first #define se second #define pb push_back #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' #define eps 1e-6 #define mem(n,a) memset(n,a,sizeof(n)) #define rep(i,be,en) for(int i=be;i<=en;++i) #define pre(i,be,en) for(int i=en;i>=be;--i) inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 100100; int a[N]; struct node { int l, r; LL sum, add; }tr[N << 2]; void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } void pushdown(int u) { node& root = tr[u]; node& left = tr[u << 1]; node& right = tr[u << 1 | 1]; if (root.add) { left.sum += (LL)(left.r - left.l + 1) * root.add; right.sum += (LL)(right.r - right.l + 1) * root.add; left.add += root.add; right.add += root.add; root.add = 0; } } void build(int u, int l, int r) { if (l == r) { tr[u] = { r,r,(LL)a[r],0 }; } else { tr[u].l = l, tr[u].r = r; int mid = l + r >> 1; build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r); pushup(u); } } void modify(int u, int l, int r, int d) { if (tr[u].l >= l && tr[u].r <= r) { tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d; tr[u].add += d; } else { pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid)modify(u << 1, l, r, d); if (r > mid)modify(u << 1 | 1, l, r, d); pushup(u); } } LL query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r)return tr[u].sum; pushdown(u); int mid = tr[u].l + tr[u].r >> 1; LL sum = 0; if (l <= mid)sum = query(u << 1, l, r); if (r > mid)sum += query(u << 1 | 1, l, r); return sum; } int main() { int n, m;scanf("%d%d", &n, &m); for (int i = 1; i <= n;++i)scanf("%d", &a[i]); build(1, 1, n); char op[2]; int l, r, d; while (m--) { scanf("%s%d%d", op, &l, &r); if (op[0] == 'Q') { printf("%lld\n", query(1, l, r)); } else { scanf("%d", &d); modify(1, l, r, d); } } return 0; }
