计蒜客 难题题库 小A的题

缘起

群里的题 计蒜客 难题题库 小A的题

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
描述
由于小 A 实在是太菜了，因此他现在需要你的帮助： 现在小 A 手上有一个凌乱的 01 串，他想通过若干次对于这
个 01 串的局部排序将它变成一个有趣的 01 序列。 现在有两种操作：
l r 0 表示把区间 [l,r] 给升序排序
l r 1 表示把区间 [l,r] 给降序排序
然后小 A 这个菜鸡想知道在 m 次操作之后序列长啥样。

输入格式
第一行一个 01 串 S。第二行一个整数m。接下来m行每行三个整数 l,r,x，保证l <= r and x=0，1中的一个。

输出格式
m 次操作之后的 01 串

数据范围
|S| <= 1000000,m <= 500000

输出时每行末尾的多余空格，不影响答案正确性

样例输入复制
11001
1
2 4 0
样例输出复制
10011

直觉就是带延迟标记的线段树. 对此不熟悉的童鞋可以见 【1】。

但是此题写的真的是让我自闭了, 最初瞄一眼的时候，感觉很简单啊~ 不就是带延迟更新的线段树么? 但是写完之后才发现, 自己对带延迟更新线段树的理解并不到位. 经过此题, 我要将带延迟更新的线段树的算法框架系统化起来.

首先, 带延迟更新线段树的节点中有三种字段

  1. 描述区间的，例如begin、end、mid、len
  2. 业务字段，例如本题中的sum
  3. 延迟更新字段，如本题中的lazy

如果更新的时候，遇到区间完全一致的话, 就直接改一下延迟更新标记就返回. 既不需要继续深究,也不需要更新业务字段(本题是sum). 这是延迟更新. 如果是真包含的关系, 则就不能延迟更新了, 就要立即更新. 即首先pushdown, 注意, 以后规范了——规定pushdown仅仅做的事情是将当前节点的延迟标记下推到两个子节点而已（即如果当前节点有延迟更新的话，就将当前节点改成不延迟更新了，而2个子节点继承父节点的延迟标记），然后在updata方法中要立即更新当前节点（因为要供业务方法getsum查询结果）, 如果方便更新的话，就可以立即更新了（如【1】），如果不方便的话, 如【2】，就要利用子节点递归返回结果来更新当前节点. 本题也是这样. 最后对于本题，getsum这种纯业务方法是不要掺杂延迟标记的. 纯业务方法仅仅跟业务字段sum打交道就行了.

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL

const int maxn = 1000005;
char s[maxn];
int m,n;
struct SegmentTreeNode
{
	int begin,end, lazy, sum, mid, len; // mid 和 len 是区间的中点和长度, 这是为了防止反复计算, lazy是延迟字段, sum是业务字段
}segmentTree[maxn<<2];

void build(int begin, int end, int cur)
{
	segmentTree[cur].begin = begin;
	segmentTree[cur].end = end;
	segmentTree[cur].lazy = segmentTree[cur].sum = 0;
	segmentTree[cur].mid = segmentTree[cur].begin+segmentTree[cur].end>>1;
	segmentTree[cur].len = segmentTree[cur].end-segmentTree[cur].begin+1;
	if (begin==end)
	{
		segmentTree[cur].lazy = s[begin]=='0'?-1:1;
		segmentTree[cur].sum = s[begin]-'0';
		return;
	}
	int mid = segmentTree[cur].mid;
	build(begin, mid, cur<<1);
	build(mid+1, end, cur<<1|1);
	segmentTree[cur].sum = segmentTree[cur<<1].sum+segmentTree[cur<<1|1].sum;
}

inline int getsum(int cur)
{
	if (!segmentTree[cur].lazy) // 没有延迟更新,则它的sum域就是实时的
	{
		return segmentTree[cur].sum; 
	}
	else if (~segmentTree[cur].lazy) // 有延迟更新, 而且上面全是1
	{
		return segmentTree[cur].len;
	}
	return 0; // 有延迟更新, 而且上面全是0
}

void pushdown(int cur) // 将[begin, end]置为c, cur节点要下推标记了
{
	if (segmentTree[cur].lazy) // 下推标记, 前提是你得有标记, 否则下推个屁啊
	{
		segmentTree[cur<<1].lazy = segmentTree[cur<<1|1].lazy = segmentTree[cur].lazy; // 儿子们继承老子的延迟标记
		segmentTree[cur].lazy = 0; // 老子不再延迟了
	}
}

int getsum(int begin, int end, int cur)
{
	if (segmentTree[cur].lazy) // 如果掉落在一个lazy的区间上的话
	{
		return (end-begin+1)*(~segmentTree[cur].lazy?1:0);
	}
	if (segmentTree[cur].begin==begin && segmentTree[cur].end==end)
	{
		return segmentTree[cur].sum; // 如果不在lazy区间上, 但是恰好包含, 则因为不在lazy区间上, 所以该节点的sum字段就是真（即）实（时）的. 这一点是updata方法保证的.
	}
	int mid = segmentTree[cur].mid;
	if (end<=mid)
	{
		return getsum(begin, end, cur<<1);
	}
	else if (begin>mid)
	{
		return getsum(begin, end, cur<<1|1);
	}
	else
	{
		return getsum(begin, mid, cur<<1)+getsum(mid+1, end, cur<<1|1);
	}
}

void updata(int begin, int end, int c, int cur) // 将 [begin, end]置为c(本题c=0或者1), 当前处于cur节点
{
	if (segmentTree[cur].begin==begin && segmentTree[cur].end==end)
	{
		segmentTree[cur].lazy = c?1:-1; // 延迟加载, 不需要更新sum这个业务域字段
		return;
	}
	pushdown(cur); // 下推延迟标记
	int mid = segmentTree[cur].mid;
	if (end<=mid)
	{
		updata(begin, end, c, cur<<1);
	}
	else if (begin>mid)
	{
		updata(begin, end, c, cur<<1|1);
	}
	else
	{
		updata(begin, mid, c, cur<<1);
		updata(mid+1, end, c, cur<<1|1);
	}
	segmentTree[cur].sum = getsum(cur<<1)+getsum(cur<<1|1); // 立即更新当前节点的业务域sum(因为它不lazy),注意, 这里调用了getsum,而不是segmentTree[cur].sum, 因为很可能子节点中
}

void dfs(int cur)
{
	if (segmentTree[cur].lazy)
	{
		if (~segmentTree[cur].lazy) // 全部是1
		{
			for (int i = 0;i<segmentTree[cur].len; i++)
			{
				putchar('1');
			}
		}
		else // 全部是0
		{
			for (int i = 0;i<segmentTree[cur].len; i++)
			{
				putchar('0');
			}
		}
		return;
	}
	dfs(cur<<1);
	dfs(cur<<1|1);
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%s", s+1);
	scanf("%d", &m);
	n = strlen(s+1);
	build(1,n,1);
	while(m--)
	{
		int l,r,x;
		scanf("%d%d%d", &l,&r,&x);
		int d = getsum(l,r,1);
		if (!d||d==r-l+1)
		{
			continue;
		}
		updata(l,r,0,1); // 先全部置零
		if (x) // 单调下降, 即[l,l+d-1]置1
		{
			updata(l,l+d-1,1,1);
		}
		else // 单调上升, 即[r-d+1,r]置1
		{
			updata(r-d+1,r,1,1);
		}
	}
	dfs(1); // 递归打印解,这没什么好说的
	return 0;
}

ac情况

正确通过 2019-10-13 10:41 849ms 94932kB c++

就本题思路而言, 最重要的是下面这种观点. 每次(l,x,r) 操作等效于如下操作

  1. 首先计算[l,r]范围内的1的个数——其实就是sum域,设为d， 如果d=0或者r-l+1, 则不论x是0（单调增）还是1（单调减），都是没有影响的, 即可以略过（continue）
  2. 否则的话, 就先把[l,r] updata为0,
  3. 如果x=0，则将[r-d+1,r] updata为1（单调增）, 否则将 [l,l+d-1] updata为0（单调降）

而updata遵从的就是上面线段树延迟更新的策略.

参考

【1】https://yfsyfs.github.io/2019/07/13/%E7%BA%BF%E6%AE%B5%E6%A0%91-fzu-2171-%E9%98%B2%E5%AE%88%E9%98%B5%E5%9C%B0-II/

【2】https://yfsyfs.github.io/2019/09/03/poj-2991-Crane-%E7%BA%BF%E6%AE%B5%E6%A0%91/