poj3468(lazy标记）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//poj3468区间成段更新，使用lazy标记
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=100005;
long long sum[maxn<<2],cov[maxn<<2];
int a[maxn];
void Pushup(int p)
{
sum[p]=sum[p<<1]+sum[p<<1|1]; //该区间小棒的质量和
}
void Pushdown(int p,int m) //将该区间的标记向子女节点传递
{
if(cov[p]){
cov[p<<1]+=cov[p];
cov[p<<1|1]+=cov[p];
sum[p<<1]+=(m-(m/2))*cov[p];
sum[p<<1|1]+=(m/2)*cov[p];
cov[p]=0; //取消当前节点的标记
}
}
void Build(int p,int l,int r)
{
cov[p]=0;
if(l==r) { sum[p]=a[l];return;}
int mid=(l+r)/2;
Build(p<<1,l,mid);
Build(p<<1|1,mid+1,r);
Pushup(p);
}
void Update(int p,int l,int r,int x,int y,int c)
{
if(x<=l&&y>=r){
cov[p]+=c;
sum[p]+=c*(r-l+1);
return;
}
Pushdown(p,r-l+1);
int mid=(l+r)/2;
if(x<=mid) Update(p<<1,l,mid,x,y,c);
if(y>mid) Update(p<<1|1,mid+1,r,x,y,c);
Pushup(p);
}
long long Query(int p,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return sum[p];
Pushdown(p,r-l+1); //询问时也要更新lazy标记
int mid=(l+r)/2;
if(y<=mid) return Query(p<<1,l,mid,x,y);
else if(x>mid) return Query(p<<1|1,mid+1,r,x,y);
else return (Query(p<<1,l,mid,x,mid)+Query(p<<1|1,mid+1,r,mid+1,y));
}
int main()
{
int n,x,y,z,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
Build(1,1,n);
char s[5];
while(q--)
{
scanf("%s",s);
if(s[0]=='Q'){
scanf("%d%d",&x,&y);
cout<<Query(1,1,n,x,y)<<endl;
}
else{
scanf("%d%d%d",&x,&y,&z);
Update(1,1,n,x,y,z);
}
}
return 0;
}
/*
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
*/