[题解] [SCOI2010] 序列操作
发表更新编程 / OI / 题解13 分钟读完 (大约1935个字)

[题解] [SCOI2010] 序列操作

题目链接

题目大意

给定一个01序列，要求支持如下操作：

  • 区间赋值
  • 区间取反
  • 查询区间内1的个数
  • 查询区间内最多有多少个连续的1

题目思路

就是一个基本的线段树，不过我借这次机会完善了一下我的线段树的基本结构

这个结构还是很完善和解耦的，可以在大部分题目里面使用，代码较为简洁且思路清晰

代码基本思路

我们首先定义序列的数据类型为V，比如本题中V为bool

我们需要两个结构体

  • Data

    记录一个线段树节点所有需要维护的值和本区间的长度

  • Tag

    记录一个线段树节点待下传的修改标记

它们分别需要实现以下方法（方法名可有不同，方便理解即可）：

  • Data
1
2
3
void init(const V &); //用一个值来初始化线段树节点（要求是叶子节点）
void merge(const Data &, const Data &); //将左右两个Data合并为自己
//其他题目中要求的操作，比如本题中有set赋值,reverse反转
  • Tag
1
2
3
4
operator bool(); //返回该Tag是否需要下传
void operator+=(const Tag &); //将自己和另一个Tag合并
void apply(const Data &); //将自己代表的修改应用于一个Data上
void clear(); //清除Tag带有的下传标记

代码实现

首先是一些常用的宏定义ww

1
2
3
4
5
typedef const int &iint; //iint代表不变的变量，通常在传参中用到，据说有助于优化内存
#define ls (x<<1) //左儿子
#define rs (ls|1) //右儿子
#define LL ls,l,mid //左儿子所需要传的参，由此build(ls,l,mid)就可以简化为build(LL)
#define RR rs,mid+1,r //与上面类似

对于本题来讲，我们的Data中需要维护

1
2
3
4
5
6
7
int cnt; //区间中1的个数
int lsm; //区间从左边开始有多少个连续相同的数
int rsm; //区间从右边开始有多少个连续相同的数
bool ld; //区间左边第一个数
bool rd; //区间右边第一个数
int mx[2]; //区间最多连续的(0的个数/1的个数)
int len; //区间长度

具体实现

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
struct Data {
	int cnt,lsm,rsm,mx[2];
	bool ld,rd;
	int len;
	inline void init(const bool &val) { //叶子结点赋初值
		mx[val]=len=lsm=rsm=1;
		cnt=ld=rd=val;
	}
	inline void set(const bool &val) { //区间赋值
		lsm=rsm=len;
		cnt=len*val;
		mx[val]=len,mx[!val]=0;
		ld=rd=val;
	}
	inline void reverse() { //区间反转
		ld=!ld,rd=!rd,cnt=len-cnt;
		swap(mx[0],mx[1]);
	}
	inline void merge(const Data &a, const Data &b) { //将两个区间合并为自己
		len=a.len+b.len;
		cnt=a.cnt+b.cnt;
		ld=a.ld,rd=b.rd;
		lsm=a.lsm;
		if (a.lsm==a.len&&a.ld==b.ld) lsm+=b.lsm; //如果左边全是相同的，并且右区间能和左区间连上，那就加上右区间的lsm
		rsm=b.rsm;
		if (b.rsm==b.len&&b.rd==a.rd) rsm+=a.rsm; //和上面类似
		mx[0]=mx[1]=0;
		mx[a.rd]+=a.rsm;
		mx[b.ld]+=b.lsm; //简单思考一下即可明白
		mx[0]=max(mx[0],max(a.mx[0],b.mx[0]));
		mx[1]=max(mx[1],max(a.mx[1],b.mx[1]));
	}
};

我们这里将所有结点的Data记为数组 $d$

由此，我们可以轻松地写出我们的上传(pu)和建树(build)函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void pu(iint x) {
	d[x].merge(d[ls],d[rs]);
}
void build(iint x=1, iint l=1, iint r=n) {
	if (l==r) { //叶子节点
		d[x].init(a[l]);
		return;
	}
	int mid=(l+r)>>1;
	build(LL);
	build(RR);
	pu(x);
}

怎么样！代码是不是很简短ww

然后我们需要来实现我们的Tag，对于本题来说主要有以下几个部分：

1
2
bool set, sval; //分别记录当前区间是否有赋值以及赋成什么值
bool rev; //当前区间是否有反转

紧接着就是最容易出错的Tag合并部分！

我们一定要保证任意一个时刻不能出现一个Tag既有赋值又有反转的情况，因为那样我们将无法确定赋值和反转的顺序

所以我们使用如下的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Tag {
	bool set,sval;
	bool rev;
	inline operator bool() const { return set||rev; } //调用时直接用Tag t;if(t){xxx...}，就会调用这个函数把tag转换为bool
	inline void operator+=(const Tag &t) { //区间合并
		if (t.set) { //如果要求赋值
			set=1;
			sval=t.sval; //就赋成这个值
			rev=0; //同时把自己原本的反转标记清空
		} else if (t.rev) { //否则，如果要求反转
			if (set) sval=!sval; //如果自己已经有赋值了，就把自己要赋的值反转
			else rev^=1; //否则记录反转标记
		}
	}
	inline void apply(Data &d) const {
		if (set) d.set(sval);
		else if (rev) d.reverse();
	}
	inline void clear() { set=sval=rev=0; } // 清空标记
};

有了这个Tag之后，我们就可以写出我们的下传(pd)函数：

1
2
3
4
5
6
7
inline void pd(iint x) {
	Tag &t=tag[x];
	if (!t) return; //如果没有需要下传的标记，则返回
	t.apply(d[ls]),tag[ls]+=t;
	t.apply(d[rs]),tag[rs]+=t;
	t.clear();
}

update函数和query函数也易于理解

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
int ll,rr; //全局变量，记录本次修改/查询的左右端点
Tag tt; //全局变量，记录本次修改要下传的标记
void update(iint x=1, iint l=1, iint r=n) {
	if (ll<=l&&r<=rr) {
		tag[x]+=tt;
		tt.apply(d[x]);
		return;
	}
	int mid=(l+r)>>1;
	pd(x);
	if (mid>=ll) update(LL);
	if (mid<rr) update(RR);
	pu(x);
}
Data query(iint x=1, iint l=1, iint r=n) {
	if (ll<=l&&r<=rr) return d[x];
	int mid=(l+r)>>1;
	pd(x);
	// 对于只需要查询左/右区间的情况，直接返回左/右区间的查询结果
	if (mid<ll) return query(RR);
	if (mid>=rr) return query(LL);
	// 对于两个区间都有包含的情况，我们则需要合并两个区间返回的Data
	Data ret;
	ret.merge(query(LL),query(RR));
	return ret;
}

最后我们的main函数就很好写啦，下面直接贴上全部代码吧

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
122
123
124
125
126
127
128
129
130
131
132
133
134
// Mivik 2019.11.12
// **************
// 下文中R代表读入(Read())，由于题解限制并没有放上Read的实现ww
// **************
#include <iostream>
#include <cstdio>

#define endl '\n'
#define R Read()

typedef const int &iint;

const int nmax = 100005;
const int tmax = 262150;
#define ls (x<<1)
#define rs (ls|1)
#define LL ls,l,mid
#define RR rs,mid+1,r
using namespace std;

int n,m;
bool a[nmax];
int ll,rr;
bool qcnt;
struct Data {
	int cnt,lsm,rsm,mx[2];
	bool ld,rd;
	int len;
	inline void init(const bool &val) {
		mx[val]=len=lsm=rsm=1;
		cnt=ld=rd=val;
	}
	inline void set(const bool &val) {
		lsm=rsm=len;
		cnt=len*val;
		mx[val]=len,mx[!val]=0;
		ld=rd=val;
	}
	inline void reverse() {
		ld=!ld,rd=!rd,cnt=len-cnt;
		swap(mx[0],mx[1]);
	}
	inline void merge(const Data &a, const Data &b) {
		len=a.len+b.len;
		cnt=a.cnt+b.cnt;
		ld=a.ld,rd=b.rd;
		lsm=a.lsm;
		if (a.lsm==a.len&&a.ld==b.ld) lsm+=b.lsm;
		rsm=b.rsm;
		if (b.rsm==b.len&&b.rd==a.rd) rsm+=a.rsm;
		mx[0]=mx[1]=0;
		mx[a.rd]+=a.rsm;
		mx[b.ld]+=b.lsm;
		mx[0]=max(mx[0],max(a.mx[0],b.mx[0]));
		mx[1]=max(mx[1],max(a.mx[1],b.mx[1]));
	}
} d[tmax];
struct Tag {
	bool set,sval;
	bool rev;
	inline operator bool() const { return set||rev; }
	inline void operator+=(const Tag &t) {
		if (t.set) {
			set=1;
			sval=t.sval;
			rev=0;
		} else if (t.rev) {
			if (set) sval=!sval;
			else rev^=1;
		}
	}
	inline void apply(Data &d) const {
		if (set) d.set(sval);
		else if (rev) d.reverse();
	}
	inline void clear() { set=sval=rev=0; }
} tag[tmax],tt;
inline void pu(iint x) { d[x].merge(d[ls],d[rs]); }
inline void pd(iint x) {
	Tag &t=tag[x];
	if (!t) return;
	t.apply(d[ls]),tag[ls]+=t;
	t.apply(d[rs]),tag[rs]+=t;
	t.clear();
}
void build(iint x=1, iint l=1, iint r=n) {
	if (l==r) {
		d[x].init(a[l]);
		return;
	}
	int mid=(l+r)>>1;
	build(LL);
	build(RR);
	pu(x);
}
void update(iint x=1, iint l=1, iint r=n) {
	if (ll<=l&&r<=rr) {
		tag[x]+=tt;
		tt.apply(d[x]);
		return;
	}
	int mid=(l+r)>>1;
	pd(x);
	if (mid>=ll) update(LL);
	if (mid<rr) update(RR);
	pu(x);
}
Data query(iint x=1, iint l=1, iint r=n) {
	if (ll<=l&&r<=rr) return d[x];
	int mid=(l+r)>>1;
	pd(x);
	if (mid<ll) return query(RR);
	if (mid>=rr) return query(LL);
	Data ret;
	ret.merge(query(LL),query(RR));
	return ret;
}
int main() {
	int i;
	n=R,m=R;
	for (i=1;i<=n;i++) a[i]=R;
	build();
	while (m--) {
		i=R,ll=R+1,rr=R+1; //本次操作的左右端点
		switch (i) {
			case 0:tt={1,0,0};update();break;
			case 1:tt={1,1,0};update();break;
			case 2:tt={0,0,1};update();break;
			case 3:cout<<query().cnt<<endl;break;
			case 4:cout<<query().mx[1]<<endl;break;
		}
	}
	return 0;
}

欢迎来我的博客逛逛

[题解] [SCOI2010] 序列操作

https://mivik.gitee.io/2019/solution/scoi2010-sequence-operations/

作者

Mivik

发布于

2019-11-12

更新于

2024-11-22

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

关注我

链接

最新文章

订阅更新

×