情之所至,甘之如饴

一道让人揪心的题——线段树2


调这两道题调了整整五小时,虽然耗费了很多时间,但这道题让我对线段树的理解变得更加的清晰、透彻,也许这份付出还是值得的。

开始之前,我们先来回顾一下线段树的几种写法:

  1. 指针版线段树

    1
    2
    3
    4
    5
    struct node
    {
    int l,r,sum,lazy;
    node *lson,*rson;
    }*root,pool[maxn<<2];
  2. 结构体版线段树(基于数组)

    1
    2
    3
    4
    struct node
    {
    int l,r,sum,lazy;
    }a[maxn<<2];
  3. 纯数组版线段树

    1
    2
    3
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    int val[maxn<<2],add[maxn<<2],mul[maxn<<2];

根据本人亲测,对于同一道题目,三种方法的运行速度大小关系为1>3>2(均能保证AC,不会TLE),按照实现时的错误率高低排序为1>2>3.

指针错误率高的原因是在定义及维护时容易写错从而出现野指针(空指针),且对于不同题目条件较难转化。

于是在指针版线段树上花了3小时,至今没有调好,故本题采用第3种方法:数组版线段树。

题目描述


如题,已知一个数列,你需要进行下面三种操作:

1.将某区间每一个数乘上x

2.将某区间每一个数加上x

3.求出某区间每一个数的和

输入输出格式

输入格式:


第一行包含三个整数N、M、P,分别表示该数列数字的个数、操作的总个数和模数。

第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数,表示一个操作,具体如下:

操作1: 格式:1 x y k 含义:将区间[x,y]内每个数乘上k

操作2: 格式:2 x y k 含义:将区间[x,y]内每个数加上k

操作3: 格式:3 x y 含义:输出区间[x,y]内每个数的和对P取模所得的结果

输出格式:


输出包含若干行整数,即为所有操作3的结果。

输入输出样例

输入样例#1: 复制

5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4

</div>

输出样例#1: 复制

17
2

</div>
</div>

说明


时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=8,M<=10

对于70%的数据:N<=1000,M<=10000

对于100%的数据:N<=100000,M<=100000

(数据已经过加强^_^)

解题思路


除了考察线段树的区间查询、区间加等基本操作,本题还加入了区间乘。因此我们要维护两个lazytag,乘法的优先级大于加法的优先级。所有的修改操作均可以直接取模,对结果无影响。

于是我就写出了一份代码:

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#define I inline
#define maxn 100010
template<class T>void read(T &x) {
register ll c = getchar(), f = 1; x = 0;
while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
int mod;
ll val[maxn<<2],add[maxn<<2],mul[maxn<<2];
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
void pushup(int rt)
{
val[rt]=(val[rt<<1]+val[rt<<1|1])%mod;
}
void build(int l,int r,int rt)
{
mul[rt]=1;
add[rt]=0;
if(l==r)
{
scanf("%lld",&val[rt]);
val[rt]%=mod;
return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void pushdown(int l,int r,int rt)
{
int m=(l+r)>>1;
val[rt<<1]=(val[rt<<1]*mul[rt]+add[rt]*(m-l+1))%mod;
val[rt<<1|1]=(val[rt<<1|1]*mul[rt]+add[rt]*(r-m))%mod;
mul[rt<<1]=(mul[rt<<1]*mul[rt])%mod;
mul[rt<<1|1]=(mul[rt<<1|1]*mul[rt])%mod;
add[rt<<1]=(add[rt<<1]*mul[rt]+add[rt])%mod;
add[rt<<1|1]=(add[rt<<1|1]*mul[rt]+add[rt])%mod;
mul[rt]=1;
add[rt]=0;
return ;
}
void Mul(int L,int R,ll c,int l,int r,int rt)
{
if(L<=l && r<=R)
{
val[rt]=(val[rt]*c)%mod;
mul[rt]=(mul[rt]*c)%mod;
add[rt]=(add[rt]%c)%mod;
return ;
}
pushdown(l,r,rt);
int m=(l+r)>>1;
if(L<=m) Mul(L,R,c,lson);
if(R>m) Mul(L,R,c,rson);
pushup(rt);
return ;
}
void Add(int L,int R,ll c,int l,int r,int rt)
{
if(L<=l && r<=R)
{
add[rt]=(add[rt]+c)%mod;
val[rt]=(val[rt]+c*(r-l+1))%mod;
return ;
}
pushdown(l,r,rt);
int m=(l+r)>>1;
if(L<=m) Add(L,R,c,lson);
if(R>m) Add(L,R,c,rson);
pushup(rt);
return ;
}
ll query(int L,int R,int l,int r,int rt)
{
if(L<=l && r<=R) return val[rt]%mod;
pushdown(l,r,rt);
int m=(l+r)>>1;
ll ret=0;
if(L<=m) ret=(ret+query(L,R,lson))%mod;
if(R>m) ret=(ret+query(L,R,rson))%mod;
return ret;
}
int n,m;
int main()
{
scanf("%d%d%d",&n,&m,&mod);
build(1,n,1);
while(m--)
{
ll op,x,y;
ll k;
scanf("%lld",&op);
if(op==1)
{
scanf("%lld%lld%lld",&x,&y,&k);
Mul(x,y,k,1,n,1);
}
else if(op==2)
{
scanf("%lld%lld%lld",&x,&y,&k);
Add(x,y,k,1,n,1);
}
else
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",query(x,y,1,n,1)%mod);
}
}
return 0;
}

这份代码交上去,居然全部WA了,于是心烦意乱的我又查了差不多一个小时,发现思路没有错误啊?只能是实现出错了。

首先,查build函数,看是否有数组越界、空指针、重复定义等,然而 并没有。

于是我又检查了pushdown和pushup函数,完全没有问题;

Add,Mul,Query三个函数的原理是相同的,于是开始查这三个。

查了大约四十分钟,我的目光聚焦在了Mul函数上:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Mul(int L,int R,ll c,int l,int r,int rt)
{
if(L<=l && r<=R)
{
val[rt]=(val[rt]*c)%mod;
mul[rt]=(mul[rt]*c)%mod;
add[rt]=(add[rt]%c)%mod;
return ;
}
pushdown(l,r,rt);
int m=(l+r)>>1;
if(L<=m) Mul(L,R,c,lson);
if(R>m) Mul(L,R,c,rson);
pushup(rt);
return ;
}

最后发现是函数开始执行时的特判和返回出了问题:

1
2
3
4
5
6
7
if(L<=l && r<=R)
{
val[rt]=(val[rt]*c)%mod;
mul[rt]=(mul[rt]*c)%mod;
add[rt]=(add[rt]%c)%mod;
return ;
}

add函数怎么能%呢?果断改为*,
于是就AC了。

AC代码(线段树2)


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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#define I inline
#define maxn 100010
template<class T>void read(T &x) {
register ll c = getchar(), f = 1; x = 0;
while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
ll p;
ll val[maxn<<2],add[maxn<<2],mul[maxn<<2];
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
void pushup(ll rt)
{
val[rt]=(val[rt<<1]+val[rt<<1|1])%p;
}
void build(ll l,ll r,ll rt)
{
mul[rt]=1;
add[rt]=0;
if(l==r)
{
scanf("%lld",&val[rt]);
val[rt]%=p;
return ;
}
ll m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void pushdown(ll l,ll r,ll rt)
{
ll m=(l+r)>>1;
val[rt<<1]=(val[rt<<1]*mul[rt]+add[rt]*(m-l+1))%p;
val[rt<<1|1]=(val[rt<<1|1]*mul[rt]+add[rt]*(r-m))%p;
mul[rt<<1]=(mul[rt<<1]*mul[rt])%p;
mul[rt<<1|1]=(mul[rt<<1|1]*mul[rt])%p;
add[rt<<1]=(add[rt<<1]*mul[rt]+add[rt])%p;
add[rt<<1|1]=(add[rt<<1|1]*mul[rt]+add[rt])%p;
mul[rt]=1;
add[rt]=0;
return ;
}
void Mul(ll L,ll R,ll c,ll l,ll r,ll rt)
{
if(L<=l && r<=R)
{
val[rt]=(val[rt]*c)%p;
mul[rt]=(mul[rt]*c)%p;
add[rt]=(add[rt]*c)%p;
return ;
}
ll m=(l+r)>>1;
pushdown(l,r,rt);
if(L<=m) Mul(L,R,c,lson);
if(R>m) Mul(L,R,c,rson);
pushup(rt);
return ;
}
void Add(ll L,ll R,ll c,ll l,ll r,ll rt)
{
if(L<=l && r<=R)
{
add[rt]=(add[rt]+c)%p;
val[rt]=(val[rt]+c*(r-l+1))%p;
return ;
}
ll m=(l+r)>>1;
pushdown(l,r,rt);
if(L<=m) Add(L,R,c,lson);
if(R>m) Add(L,R,c,rson);
pushup(rt);
return ;
}
ll query(ll L,ll R,ll l,ll r,ll rt)
{
if(L<=l && r<=R) return val[rt]%p;
ll m=(l+r)>>1;
pushdown(l,r,rt);
ll ret=0;
if(L<=m) ret=(ret+query(L,R,lson))%p;
if(R>m) ret=(ret+query(L,R,rson))%p;
return ret;
}
ll n,m;
int main()
{
scanf("%lld%lld%lld",&n,&m,&p);
build(1,n,1);
while(m--)
{
ll op,x,y;
ll k;
scanf("%lld",&op);
if(op==1)
{
scanf("%lld%lld%lld",&x,&y,&k);
Mul(x,y,k,1,n,1);
}
else if(op==2)
{
scanf("%lld%lld%lld",&x,&y,&k);
Add(x,y,k,1,n,1);
}
else
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",query(x,y,1,n,1)%p);
}
}
return 0;
}

下面,我们再来看“维护序列”这道题目:

[AHOI2009]维护序列

题目描述


老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。 有长为N的数列,不妨设为a1,a2,…,aN 。有如下三种操作形式: (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模P的值。

输入输出格式


输入格式:

第一行两个整数N和P(1≤P≤1000000000)。 第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。 第三行有一个整数M,表示操作总数。 从第四行开始每行描述一个操作,输入的操作有以下三种形式: 操作1:“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。 操作2:“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3:“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。

输出格式:

对每个操作3,按照它在输入中出现的顺序,依次输出一行一个整数表示询问结果。

输入输出样例

输入样例#1: 复制

7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7

</div>

输出样例#1: 复制

2
35
8

</div>
</div>

说明


【样例说明】

初始时数列为(1,2,3,4,5,6,7)。

经过第1次操作后,数列为(1,10,15,20,25,6,7)。

对第2次操作,和为10+15+20=45,模43的结果是2。

经过第3次操作后,数列为(1,10,24,29,34,15,16}

对第4次操作,和为1+10+24=35,模43的结果是35。

对第5次操作,和为29+34+15+16=94,模43的结果是8。

测试数据规模如下表所示

数据编号 1 2 3 4 5 6 7 8 9 10

N= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000

M= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000

Source: Ahoi 2009

解题思路


本题除了读入数据的顺序,都和线段树2完全一样,简直就是量身定制的模板题。

于是依题意改了读入顺序之后,完美AC。

代码实现-序列维护


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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#define I inline
#define maxn 100010
template<class T>void read(T &x) {
register ll c = getchar(), f = 1; x = 0;
while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
ll p;
ll val[maxn<<2],add[maxn<<2],mul[maxn<<2];
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
void pushup(ll rt)
{
val[rt]=(val[rt<<1]+val[rt<<1|1])%p;
}
void build(ll l,ll r,ll rt)
{
mul[rt]=1;
add[rt]=0;
if(l==r)
{
scanf("%lld",&val[rt]);
val[rt]%=p;
return ;
}
ll m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void pushdown(ll l,ll r,ll rt)
{
ll m=(l+r)>>1;
val[rt<<1]=(val[rt<<1]*mul[rt]+add[rt]*(m-l+1))%p;
val[rt<<1|1]=(val[rt<<1|1]*mul[rt]+add[rt]*(r-m))%p;
mul[rt<<1]=(mul[rt<<1]*mul[rt])%p;
mul[rt<<1|1]=(mul[rt<<1|1]*mul[rt])%p;
add[rt<<1]=(add[rt<<1]*mul[rt]+add[rt])%p;
add[rt<<1|1]=(add[rt<<1|1]*mul[rt]+add[rt])%p;
mul[rt]=1;
add[rt]=0;
return ;
}
void Mul(ll L,ll R,ll c,ll l,ll r,ll rt)
{
if(L<=l && r<=R)
{
val[rt]=(val[rt]*c)%p;
mul[rt]=(mul[rt]*c)%p;
add[rt]=(add[rt]*c)%p;
return ;
}
ll m=(l+r)>>1;
pushdown(l,r,rt);
if(L<=m) Mul(L,R,c,lson);
if(R>m) Mul(L,R,c,rson);
pushup(rt);
return ;
}
void Add(ll L,ll R,ll c,ll l,ll r,ll rt)
{
if(L<=l && r<=R)
{
add[rt]=(add[rt]+c)%p;
val[rt]=(val[rt]+c*(r-l+1))%p;
return ;
}
ll m=(l+r)>>1;
pushdown(l,r,rt);
if(L<=m) Add(L,R,c,lson);
if(R>m) Add(L,R,c,rson);
pushup(rt);
return ;
}
ll query(ll L,ll R,ll l,ll r,ll rt)
{
if(L<=l && r<=R) return val[rt]%p;
ll m=(l+r)>>1;
pushdown(l,r,rt);
ll ret=0;
if(L<=m) ret=(ret+query(L,R,lson))%p;
if(R>m) ret=(ret+query(L,R,rson))%p;
return ret;
}
ll n,m;
int main()
{
scanf("%lld%lld",&n,&p);
build(1,n,1);
scanf("%lld",&m);
while(m--)
{
ll op,x,y;
ll k;
scanf("%lld",&op);
if(op==1)
{
scanf("%lld%lld%lld",&x,&y,&k);
Mul(x,y,k,1,n,1);
}
else if(op==2)
{
scanf("%lld%lld%lld",&x,&y,&k);
Add(x,y,k,1,n,1);
}
else
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",query(x,y,1,n,1)%p);
}
}
return 0;
}

不得不说数组版线段树真好用,实现难度小、错误率低,适合新手使用。

暑期会练一练数据结构,还会分享一些题目的解法,敬请期待。

 评论



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:726.4k