C++-POJ3468-A Simple Problem with Integers Lineup[线段树区间修改区间查询]

 1 #include <cstdio>
 2 #include <iostream>
 3 using namespace std;
 4 typedef long long ll;
 5 const int MAXN=1e5+10;
 6 struct node{ll sum,add;}t[MAXN<<2];
 7 int L,R;ll d;
 8 
 9 #define ls rt<<1
10 #define rs rt<<1|1
11 
12 void push_up(int rt){t[rt].sum=t[ls].sum+t[rs].sum;}
13 void push_down(int rt,int l,int r,int mid){
14     if(t[rt].add){
15         t[ls].add+=t[rt].add;
16         t[rs].add+=t[rt].add;
17         t[ls].sum+=(mid-l+1)*t[rt].add;
18         t[rs].sum+=(r-mid)*t[rt].add;
19         t[rt].add=0;
20     }
21 }
22 
23 void build(int rt,int l,int r){
24     if(l==r){scanf("%lld",&t[rt].sum);return;}
25     int mid=(l+r)>>1;
26     build(ls,l, mid);
27     build(rs,mid+1,r);
28     push_up(rt);
29 }
30 
31 void update(int rt,int l,int r){
32     if(L<=l&&r<=R){t[rt].sum+=(r-l+1)*d,t[rt].add+=d;return;}
33     int mid=(l+r)>>1;
34     push_down(rt,l,r,mid);
35     if(L<=mid)update(ls,l,mid);
36     if(R>mid)update(rs,mid+1,r);
37     push_up(rt);
38 }
39 
40 ll query(int rt, int l, int r){
41     if(L<=l&&r<=R)return t[rt].sum;
42     int mid=(l+r)>>1;
43     push_down(rt,l,r,mid);
44     ll ans=0;
45     if(L<=mid)ans+=query(ls,l,mid);
46     if(R>mid)ans+=query(rs,mid+1,r);
47     return ans;
48 }
49 
50 int main(){
51     int n,m;
52     scanf("%d%d",&n,&m);
53     build(1,1,n);
54     for(char s[3];m--;){
55         scanf("%s",s);
56         if(s[0]=='C')scanf("%d%d%lld",&L,&R,&d),update(1,1,n);
57         else scanf("%d%d",&L,&R),printf("%lld
",query(1,1,n));
58     }
59     return 0;
60 }