一个简单的整数问题

题目描述

你有N个整数，A1，A2，…，AN。 你需要处理两种操作。 一种操作是在给定间隔中为每个数字添加一些给定数字。 另一种是要求给定间隔中的数字总和。

输入

第一行包含两个数字N和Q.1≤N，Q≤100000。
第二行包含N个数字，A1，A2，…，AN的初始值。 -1000000000≤AI≤1000000000。
接下来的Q行中的每一行代表一个操作。
“C a b c”表示将C添加到Aa，Aa + 1，…，Ab中的每一个。 -10000≤c≤10000。
“Q a b”表示查询Aa，Aa + 1，…，Ab的总和。

输出

你需要回到Q个询问，每个询问一行。

样例输入

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
样例输出
4
55
9
15

提示

总和可能超过32位整数的范围。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100010;
int n,m;
int w[N];
struct node{int l,r;ll sum,add;
}t[4*N];
void pushup(int u)
{t[u].sum=t[u<<1].sum+t[u<<1|1].sum;
}
void pushdown(int u)
{if(t[u].add){t[u<<1].add+=t[u].add,t[u<<1].sum+=(ll)(t[u<<1].r-t[u<<1].l+1)*t[u].add;t[u<<1|1].add+=t[u].add,t[u<<1|1].sum+=(ll)(t[u<<1|1].r-t[u<<1|1].l+1)*t[u].add;t[u].add=0;}
} 
void build(int u,int l,int r)
{   t[u].l=l,t[u].r=r;if(l==r){t[u].sum=w[r],t[u].add=0;} else{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(t[u].l>=l&&t[u].r<=r){t[u].sum+=(ll)(t[u].r-t[u].l+1)*d;t[u].add+=d;}else{pushdown(u);int mid=t[u].l+t[u].r>>1;if(mid>=l) 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(t[u].l>=l&&t[u].r<=r) return t[u].sum;pushdown(u);int mid=t[u].l+t[u].r>>1;ll sum=0;if(mid>=l) sum=query(u<<1,l,r);if(mid<r) sum+=query(u<<1|1,l,r);return sum;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&w[i]);build(1,1,n);char op[2];int l,r,d;while(m--){scanf("%s%d%d",op,&l,&r);if(*op=='C'){scanf("%d",&d);modify(1,l,r,d);}else printf("%lld\n",query(1,l,r));}return 0;
}