poj 3468

125 阅读 0 评论 83 点赞

我是靠谱客的博主老实摩托，这篇文章主要介绍poj 3468，现在分享给大家，希望可以做个参考。

题目：http://poj.org/problem?id=3468

成段更新线段树。用mark延迟标记，在更新的时候不用每次把叶子节点全部更新，只需要把需要更新的一段所需要更新的权值标记一下，然后在下次查询的时候。如果需要更新这个被标记的子节点。那么把这个子节点的儿子节点的延迟mark加上父亲节点的mark。

下面是AC代码：

复制代码

#include<cstdio>
using namespace std;
#define maxn 100000+10
typedef long long LL;
struct node{
int l,r,m;
LL sum,mark;
}T[maxn<<2];
int a[maxn];
void build(int id,int l,int r){
T[id].l=l;
T[id].r=r;
T[id].m=(l+r)>>1;
T[id].mark=0;
if(l==r)
{ T[id].sum=a[l]; return;
}
int m=(l+r)>>1;
build(id<<1,l,m);
build((id<<1)+1,m+1,r);
T[id].sum=(T[id<<1].sum+T[(id<<1)+1].sum);
}
void update(int id,int l,int r,int val){
if(T[id].l==l&&T[id].r==r){
T[id].mark+=val; return ;
}
T[id].sum+=(LL)val*(r-l+1);
if(T[id].m>=r)
update(id<<1,l,r,val);
else if(T[id].m<l)
update((id<<1)+1,l,r,val);
else{
update(id<<1,l,T[id].m,val);
update((id<<1)+1,T[id].m+1,r,val);
}
}
LL query(int id,int l,int r){
if(T[id].l==l&&T[id].r==r)
return T[id].sum+T[id].mark*(LL)(r-l+1);
if(T[id].mark!=0) {
T[id<<1].mark+=T[id].mark;
T[(id<<1)+1].mark+=T[id].mark;
T[id].sum+=(LL)(T[id].r-T[id].l+1)*T[id].mark;
T[id].mark=0;
}
if(T[id].m>=r){
return query(id<<1,l,r);
}
else if(T[id].m<l){
return query((id<<1)+1,l,r);
}
else{
return query(id<<1,l,T[id].m)+query((id<<1)+1,T[id].m+1,r);
}
}
int main(){
int n,Q;
char str[8];
int b,c,d;
while(scanf("%d%d",&n,&Q)!=EOF){
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
for(int i=0;i<Q;i++){
scanf("%s",str);
if(str[0]=='Q'){
scanf("%d%d",&b,&c);
printf("%lldn",query(1,b,c));
}
else if(str[0]=='C'){
scanf("%d%d%d",&b,&c,&d);
update(1,b,c,d);
}
}
}
return 0;
}

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
#include<cstdio>
using namespace std;
#define maxn 100000+10
typedef long long LL;
struct node{
int l,r,m;
LL sum,mark;
}T[maxn<<2];
int a[maxn];
void build(int id,int l,int r){
T[id].l=l;
T[id].r=r;
T[id].m=(l+r)>>1;
T[id].mark=0;
if(l==r)
{ T[id].sum=a[l]; return;
}
int m=(l+r)>>1;
build(id<<1,l,m);
build((id<<1)+1,m+1,r);
T[id].sum=(T[id<<1].sum+T[(id<<1)+1].sum);
}
void update(int id,int l,int r,int val){
if(T[id].l==l&&T[id].r==r){
T[id].mark+=val; return ;
}
T[id].sum+=(LL)val*(r-l+1);
if(T[id].m>=r)
update(id<<1,l,r,val);
else if(T[id].m<l)
update((id<<1)+1,l,r,val);
else{
update(id<<1,l,T[id].m,val);
update((id<<1)+1,T[id].m+1,r,val);
}
}
LL query(int id,int l,int r){
if(T[id].l==l&&T[id].r==r)
return T[id].sum+T[id].mark*(LL)(r-l+1);
if(T[id].mark!=0) {
T[id<<1].mark+=T[id].mark;
T[(id<<1)+1].mark+=T[id].mark;
T[id].sum+=(LL)(T[id].r-T[id].l+1)*T[id].mark;
T[id].mark=0;
}
if(T[id].m>=r){
return query(id<<1,l,r);
}
else if(T[id].m<l){
return query((id<<1)+1,l,r);
}
else{
return query(id<<1,l,T[id].m)+query((id<<1)+1,T[id].m+1,r);
}
}
int main(){
int n,Q;
char str[8];
int b,c,d;
while(scanf("%d%d",&n,&Q)!=EOF){
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
for(int i=0;i<Q;i++){
scanf("%s",str);
if(str[0]=='Q'){
scanf("%d%d",&b,&c);
printf("%lldn",query(1,b,c));
}
else if(str[0]=='C'){
scanf("%d%d%d",&b,&c,&d);
update(1,b,c,d);
}
}
}
return 0;
}