【板子】

线段树

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<iostream>
 6 using namespace std;
 7 
 8 #define maxn 200000
 9 
10 int n,m,fg,a,b;
11 long long x;
12 int num[maxn+5];
13 
14 struct tree{
15     int l;
16     int r;
17     long long sum;
18     int lazy;
19 }t[maxn*4+5];
20 
21 void pushup(int u){
22     t[u].sum=t[u<<1].sum+t[u<<1|1].sum;
23 }
24 
25 void pushdown(int u){
26     if(t[u].lazy){
27         t[u<<1].lazy+=t[u].lazy;
28         t[u<<1|1].lazy+=t[u].lazy;
29         t[u<<1].sum+=(t[u<<1].r-t[u<<1].l+1)*t[u].lazy;
30         t[u<<1|1].sum+=(t[u<<1|1].r-t[u<<1|1].l+1)*t[u].lazy;
31         t[u].lazy=0;
32     }
33 }
34 
35 void build(int u,int l,int r){
36     t[u].l=l;
37     t[u].r=r;
38     t[u].lazy=0;
39     if(l==r){
40         t[u].sum=num[l];
41         return;
42     }
43     int mid=(l+r)>>1;
44     build(u<<1,l,mid);
45     build(u<<1|1,mid+1,r);
46     pushup(u);
47 }
48 
49 void update(int u,int l,int r,long long x){
50     if(t[u].l>=l&&t[u].r<=r){
51         t[u].lazy+=x;
52         t[u].sum+=(t[u].r-t[u].l+1)*x;
53         return;
54     }
55     pushdown(u);
56     int mid=(t[u].l+t[u].r)>>1;
57     if(l<=mid)update(u<<1,l,r,x);
58     if(r>mid)update(u<<1|1,l,r,x);
59     pushup(u);
60 }
61 
62 long long query(int u,int l,int r){
63     if(t[u].l>=l&&t[u].r<=r)return t[u].sum;
64     pushdown(u);
65     int mid=(t[u].l+t[u].r)>>1;
66     long long ans=0;
67     if(l<=mid)ans+=query(u<<1,l,r);
68     if(r>mid)ans+=query(u<<1|1,l,r);
69     return ans;
70 }
71 
72 int main(){
73     cin>>n;
74     for(int i=1;i<=n;i++)
75         cin>>num[i];
76     build(1,1,n);
77     cin>>m;
78     for(int i=1;i<=m;i++){
79         cin>>fg;
80         if(fg==1){
81             cin>>a>>b>>x;
82             update(1,a,b,x);
83         }
84         else if(fg==2){
85             cin>>a>>b;
86             cout<<query(1,a,b)<<endl;
87         }
88     }
89     return 0;
90 }

View Code