周弈帆的博客
0%

HDU-6562 Lovers

Posted on In ,

Preface

本题是2018CCPC吉林站的H题。吉林站是我参加的第一场正式比赛，当时我们写的最后一题就是这道题。我在赛场上想出了正确的大致解法，却因为细节没有想全，没有在赛场中A掉这道题。也是从这次比赛开始，我所在的队伍在拿银的时候，几乎每次离金牌就差一题，而且这一题的算法已经被我们想到，只是没有写完。每场比赛打完，我的感受大多是“要是再写出一题就好了”。

时光飞逝，如今我都快退役了。我还有两场正式比赛要打，而其中一场比赛将在这个周末举办。我想在比赛前临阵磨枪，找一些代码量比较大的题来提升写代码的能力。我想起了这道当时认为比较繁琐的题目。

没想到WA了一次后，这道题就被我十分轻松的A掉了。思路清晰，大脑能量充足的情况下，这道题对我来说竟然算不上一道难题，甚至谈不上一道有代码量的题。我都不知道该怎样评价自己的水平了。该写出题的时候写不出题，训练的时候又看得过去。

不管怎样，我要给这道对我来说意义重大的题写一篇题解。

Description

数轴上有$n$个字符串，每个字符串初始为空。现在要进行$m$次以下操作：

  • 操作1：把一个$[l, r]$区间里所有字符串前面加上一位十进制数字，后面加上一位十进制数字。比如”44”这个字符串“加上”5后，就变成了”5445”.
  • 操作2：求$[l, r]$区间里所有字符串代表的数字之和。

样例组数$1\leq t\leq5$，长度$1 \leq n \leq 10^5$，操作次数$1 \leq m \leq 10^5$

Sample Input & Output

1
2
3
4
5
6
7
8
9
2
3 2
wrap 1 3 1
query 1 2
4 4
wrap 1 3 0
wrap 2 4 3
query 1 4
query 2 3
1
2
3
4
5
Case 1:
22
Case 2:
6039
6006

Solution

看到关于区间的操作、求和，第一反应肯定是线段树。

问题的关键在于，在一个数字前面和最后加了一位，这个操作的实质是什么。

假设当前某个数字是$x$，有$d$位，在它的前后放了一个$y$，那么这步操作的结果是$x \leftarrow y * 10^{d+2} + x \times10 + y$。可以发现，后面的乘法和加法都十分好维护。用两个lazy变量来标记区间该乘和该加的值。每次乘的时候还要改变加的标记。问题的关键是，前面加的那一堆东西和当前数无关，而是和当前数的位数有关。

既然操作和数位数有关，那么维护每个数的位数一定是一个可行的做法。单由于操作是对区间进行操作，一个区间里不同的数有不同的位数，这个东西哪怕可以用vector存下，合并的时间复杂度都会爆炸。有没有一种办法能够合并区间所有数的位数这个信息呢？

观察操作的式子我们可以发现，我们做的所有运算都是加法和乘法。我们不关心区间里每一个数有几位，而是要让这些数的最高位乘上一个操作数$y$再乘100，最后再加到一起。这样想的话，我们可以把每个数的最高位加起来，以获取这个区间所有数的最高位信息。比如一个区间的数是$11,2222,4444$，那么最高数位之和就是$10 + 1000 + 1000 = 2010$。那么对这个区间信息操作时，不再是$x \leftarrow y 10^{d+2} + x \times10 + y$，而是$x \leftarrow y 2010^{d+2} + x \times10 + y$。如果我们能维护一个最高数位和信息，我们就能计算出当前区间的数字和，也就是操作2询问的内容了。

现在问题就变成了如何维护区间的最高数位和及相关lazy变量。为了计算出新的$x$，我们要用$y$来乘最高数位和。由于区间操作要在线段树上下放，而父区间和子区间$y$乘最高数位和的结果是不同的。因此，我们只能每次下放$y$这个操作数。我们需要一个新的lazy变量来储存我们下放的$y$。

光存了$y$不够，因为子区间可能有没有计算过的操作数。比如子区间进行了操作数3的操作，子区间的数字应当是$3x3$，但子区间没有被访问，标记还没有计算过。现在又对整个区间进行了操作数4的操作，子区间的数字现在应当是$43x34$。此时子区间依然没有被访问。也就是说，之前lazy变量是3，经过操作后lazy变量变成了43。

每次进行操作，lazy变量前面都会加一个数。往前面加数这个操作可不好做。但是，我们可以记录这个lazy变量的最大位数。比如lazy变量现在是43，那么最大位数就是2。下次进行操作数5的操作时，$5 \times 10^2 + 43 = 543$，就能正确计算出新的lazy变量了。这个lazy变量的最大位数也是一个新的lazy变量。

所以，所有的变量我们都可以用线段树来维护，这道题就写完了。

Code

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
struct node
{
	node *l, *r;
	int preSum;
	int preMult;
	int preMove;
	int sum;
	int markSum;
	int markMult;
	int len;
	node()
	{
		l = r = nullptr;
		preSum = 1;
		len = 0;
		preMult = 0;
		markMult = 1;
		preMove = markSum = sum = 0;
	}
	void update()
	{
		sum = ((preMult * (ll)preSum) % MOD * p10[preMove] % MOD + (ll)sum * markMult % MOD + markSum * (ll)len % MOD) % MOD;
		preSum = preSum * p10[preMove * 2] % MOD;
	}
	void pushDownTo(node* l)
	{
		l->preMult = (((ll)preMult * p10[l->preMove] % MOD) + l->preMult) % MOD;
		l->preMove += preMove;
		l->markSum = ((ll)l->markSum * markMult % MOD + markSum) % MOD;
		l->markMult = (ll)l->markMult * markMult % MOD;
	}
	void pushDown()
	{
		update();
		if (l)
		{
			pushDownTo(l);
			pushDownTo(r);
		}
		clearMark();
	}
	void pushUp()
	{
		if (l)
		{
			l->pushDown();
			r->pushDown();
			preSum = (l->preSum + r->preSum) % MOD;
			sum = (l->sum + r->sum) % MOD;
		}
	}
	void setMark(int x)
	{
		preMult = x;
		preMove = 1;
		markMult = 10;
		markSum = x;
	}
	void clearMark()
	{
		preMult = preMove = markSum = 0;
		markMult = 1;
	}
};

/*………………a lot of code…………*/

void modify(int l, int r, int v, node* nd = root, int cl = 1, int cr = n)
{
	nd->pushDown();
	if (l == cl && r == cr)
	{
		nd->setMark(v);
		nd->pushDown();
	}
	else
	{
		int mid = (cl + cr) / 2;
		if (r <= mid)
		{
			modify(l, r, v, nd->l, cl, mid);
		}
		else if (l > mid)
		{
			modify(l, r, v, nd->r, mid + 1, cr);
		}
		else
		{
			modify(l, mid, v, nd->l, cl, mid);
			modify(mid + 1, r, v, nd->r, mid + 1, cr);
		}
		nd->pushUp();
	}
}

ll query(int l, int r, node* nd = root, int cl = 1, int cr = n)
{
	nd->pushDown();
	if (l == cl && r == cr)
	{
		return nd->sum;
	}
	else
	{
		int mid = (cl + cr) / 2;
		if (r <= mid)
		{
			return query(l, r, nd->l, cl, mid);
		}
		else if (l > mid)
		{
			return query(l, r, nd->r, mid + 1, cr);
		}
		else
		{
			return (query(l, mid, nd->l, cl, mid) + 
			query(mid + 1, r, nd->r, mid + 1, cr)) % MOD;
		}
	}
}

我一般是不放代码的，但我觉得这段代码写的非常有条理，所以就打算展示一下。

线段树操作的精髓在于node的操作。不管是怎样的区间操作、查询，所有modify和query都可以调同一个格式的函数，只要修改node中函数的实现细节就可以了。

len变量不是一个动态的变量，我是在建树的时候把len算了一下。

markMult和preMove似乎是相关的两个变量，但多用一个变量也不会MLE会TLE，用两个变量能够让写代码时思路更加清晰。

Review

写多了线段树的区间操作后，你就能对线段树有更深的认识。线段树本质是维护一些满足幺半群的运算，也就是一些不可逆，互相叠加的运算，比如加法、乘法、求最值。

在对区间进行操作的时候，要想清楚两件事。一个是lazy标记怎么对固有变量产生影响的，一个是操作怎么对lazy标记产生影响的。如果只是简单的加法和乘法，这两个步骤实在是过于显然，以至于问题一变复杂，我们就搞不清应该如何维护lazy变量了。只要认识了区间操作的本质，任何单纯线段树区间操作都是很简单的题。