You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
Sample Input
10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4
Sample Output
4 55 9 15
Hint
The sums may exceed the range of 32-bit integers.
傻逼poj不支持万能头文件
//#include <bits/stdc++.h> #include <stdio.h> using namespace std; typedef long long ll; const ll inf = 4e18+10; const int mod = 1000000007; const int mx = 5e6+5; //check the limits, dummy //typedef pair<int, int> pa; //const double PI = acos(-1); //ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } //#define swa(a,b) a^=b^=a^=b //#define re(i,a,b) for(int i=(a),_=(b);i<_;i++) //#define rb(i,a,b) for(int i=(b),_=(a);i>=_;i--) //#define clr(a) memset(a, 0, sizeof(a)) //#define lowbit(x) ((x)&(x-1)) //#define mkp make_pair //void sc(int& x) { scanf("%d", &x); }void sc(int64_t& x) { scanf("%lld", &x); }void sc(double& x) { scanf("%lf", &x); }void sc(char& x) { scanf(" %c", &x); }void sc(char* x) { scanf("%s", x); } ll sum[mx], add[mx]; void pushup(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void pushdown(int rt, int m) {//更新rt的子节点 if (add[rt]) { add[rt << 1] += add[rt]; add[rt << 1 | 1] += add[rt]; sum[rt << 1] += (m - (m >> 1))* add[rt]; sum[rt << 1 | 1] += (m >> 1)* add[rt]; add[rt] = 0;//取消本层标记 } } #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 void biuld(int l, int r, int rt) {//用满二叉树建树 add[rt] = 0; if (l == r) {//叶子结点，赋值 scanf("%lld", &sum[rt]); return; } int mid = (l + r) >> 1; biuld(lson); biuld(rson); pushup(rt);//向上更新区间和 } void update(int a, int b, ll c, int l, int r, int rt) {//区间更新 if (a <= l && b >= r) { sum[rt] += (r - l + 1) * c; add[rt] += c; return; } pushdown(rt, r - l + 1);//向下更新 int mid = (l + r) >> 1; if (a <= mid)update(a, b, c, lson);//分成两半深入 if (b > mid)update(a, b, c, rson); pushup(rt); } ll query(int a, int b, int l, int r, int rt) {//区间求和 if (a <= l && b >= r) return sum[rt];//满足lazy直接返回 pushdown(rt, r - l + 1); int mid = (l + r) >> 1; ll ans = 0; if (a <= mid)ans += query(a, b, lson); if (b > mid)ans += query(a, b, rson); return ans; } int main() { //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; scanf("%d", &n); scanf("%d", &m); biuld(1, n, 1); while (m--) { char str[2]; int a, b; ll c; scanf("%s", str); if (str[0] == 'C') { scanf("%d", &a); scanf("%d", &b); scanf("%lld", &c); update(a, b, c, 1, n, 1); } else { scanf("%d", &a); scanf("%d", &b); printf("%lld\n", query(a, b, 1, n, 1)); } } return 0; }