洛谷P2357守墓人题解

题解

前置知识:

  • C++
  • 数据结构

题目链接

P2357 守墓人

解题思路

线段树or树状数组裸题
本题解用的可区间更新的树状数组
数据范围会爆int,所以用long long

代码

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
85
86
87
88
89
90
91
92
#include<cstdio>
#include<cstring>
using namespace std;
long long sum[200010];
long long lazytag[200010];
int n;
inline int lowbit(int x)
{
return x&(-x);
}
long long suum(int i,long long k[])
{
long long s=0;
while(i>0)
{
s+=k[i];
i-=lowbit(i);
}
return s;
}
void update(int x,long long a,long long k[])
{
while(x<=n)
{
k[x]+=a;
x+=lowbit(x);
}
}
void uprange(int x,int y,long long a)
{
update(x,-(x-1)*a,sum);
update(x,a,lazytag);
update(y+1,y*a,sum);
update(y+1,-a,lazytag);

}
long long rangesum(int i,int j)
{
long long s=0;
s+=suum(j,sum)+suum(j,lazytag)*j;
s-=suum(i-1,sum)+suum(i-1,lazytag)*(i-1);
return s;
}
int main()
{
int f;
scanf("%d%d",&n,&f);
long long i,j,x,y,su;
int t;
memset(sum,0,sizeof(sum));
memset(lazytag,0,sizeof(lazytag));
for(i=1;i<=n;i++)
{
scanf("%d",&t);
update(i,t,sum);
}
for(i=0;i<f;i++)
{
scanf("%lld",&t);
if(t==1)
{
scanf("%lld%lld%lld",&x,&y,&su);
uprange(x,y,su);

}
if(t==2)
{
scanf("%lld",&su);

uprange(1,1,su);

}
if(t==3)
{
scanf("%d",&su);
uprange(1,1,-su);

}
if(t==4)
{
scanf("%lld%lld",&x,&y);

printf("%lld\n",rangesum(x,y));
}
if(t==5)
{
printf("%lld\n",rangesum(1,1));
}
}

}

Author

王钦砚

Posted on

2019-09-23

Licensed under

CC BY-NC-SA 4.0

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×