Zkw线段树

不带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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stack>
using namespace std;
#define R register
#define ll long long
#define fo(i,a,b) for(R int (i)=(a);(i)<=(b);++(i))
int sum[40000],dt[40000],le[40000],ri[40000];
int M,n;
void build()
{
for(M=1;M<=n;M<<=1);
fo(i,M+1,M+n)scanf("%d",&sum[i]);
fo(i,1,M)le[i+M]=ri[i+M]=i;
for(int i=M-1;i;--i)sum[i]=sum[i<<1]+sum[i<<1|1],le[i]=le[i<<1],ri[i]=ri[i<<1|1];
}
void up(int x){if(x)sum[x]=sum[x<<1]+sum[x<<1|1]+(ri[x]-le[x]+1)*dt[x];}
void change(int l,int r,int a)
{
for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1)dt[l^1]+=a,sum[l^1]+=(ri[l^1]-le[l^1]+1)*a;
if(r&1)dt[r^1]+=a,sum[r^1]+=(ri[r^1]-le[r^1]+1)*a;
up(l>>1),up(r>>1);
}
for(;l;l>>=1)up(l);
}
int query(int l,int r)
{
int ans=0,s=l,t=r;
for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1)ans+=sum[l^1];
if(r&1)ans+=sum[r^1];
if(s<=ri[l>>1])ans+=(ri[l>>1]-s+1)*dt[l>>1];
if(t>=le[r>>1])ans+=(t-le[r>>1]+1)*dt[r>>1];
}
for(l>>=1;l;l>>=1)ans+=(t-s+1)*dt[l];
return ans;
}

单点修改,区间查询

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stack>
using namespace std;
#define R register
#define ll long long
#define fo(i,a,b) for(R int (i)=(a);(i)<=(b);++(i))
int M,tree[500000],n;
void mt(int x){tree[x]=tree[x<<1]+tree[x<<1|1];}
void build()
{
for(M=1;M<n;M<<=1);
fo(i,M+1,M+n)scanf("%d",&tree[i]);
for(int i=M-1;i;--i)mt(i);
}
void update(int pos,int v)
{
pos+=M;
tree[pos]=v;
for(pos>>=1;pos;pos>>=1)mt(pos);
}
int sum(int l,int r)
{
R int ans=0;
for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1)
{
if(!(l&1))ans+=tree[l^1];
if(r&1)ans+=tree[r^1];
}
return ans;
}

区间修改,区间查询最大值(差分)

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
93
94
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
using namespace std;
#define R register
#define ll long long
#define fo(i,a,b) for(R int (i)=(a);(i)<=(b);++(i))
int n,m,M,tr[200000<<2];
void build()
{
for(M=1;M<=n;M<<=1);
fo(i,1,M)tr[i]=-1e9;M--;
for(int i=M+1;i<=M+n;++i)scanf("%d",&tr[i]);
for(int i=M;i;--i)
{
tr[i]=max(tr[i<<1],tr[i<<1|1]);
tr[i<<1]-=tr[i];tr[i<<1|1]-=tr[i];
}
}
void add(int l,int r,int x)
{
l+=M;r+=M;
if(l==r)
{
tr[l]+=x;
for(;l>1;l>>=1)
{
R int now=max(tr[l],tr[l^1]);
tr[l]-=now;tr[l^1]-=now;
tr[l>>1]+=now;
}
return;
}
tr[l]+=x;tr[r]+=x;
for(;l^r^1;l>>=1,r>>=1)
{
if(~l&1)tr[l^1]+=x;
if(r&1)tr[r^1]+=x;
R int now=max(tr[l^1],tr[l]);
tr[l]-=now;tr[l^1]-=now;
tr[l>>1]+=now;
now=max(tr[r],tr[r^1]);
tr[r]-=now;tr[r^1]-=now;
tr[r>>1]+=now;
}
while(l>1)
{
R int now=max(tr[l^1],tr[l]);
tr[l]-=now;tr[l^1]-=now;
tr[l>>1]+=now;
l>>=1;
}
}
int query(int l,int r)
{
R int ans=0,ansl=0,ansr=0;
l+=M;r+=M;
if(l==r)
{
while(l)ans+=tr[l],l>>=1;
return ans;
}
for(;l^r^1;l>>=1,r>>=1)
{
ansl+=tr[l];ansr+=tr[r];
if(~l&1)ansl=max(ansl,tr[l^1]);
if(r&1)ansr=max(ansr,tr[r^1]);
}
ansl+=tr[l];ansr+=tr[r];
ans=max(ansl,ansr);
l>>=1;
while(l)ans+=tr[l],l>>=1;
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
build();
while(m--)
{
R int l,r,odd,val;
scanf("%d%d%d",&odd,&l,&r);
if(!odd)printf("%d\n",query(l,r));
else scanf("%d",&val),add(l,r,val);
}
return 0;
}

显示 Gitment 评论