请注意，本文默认大家学过单改区查的基础线段树（包括动态开点），若未学，请移步
OI-wiki，例题可以使用树状数组的题目。
区间修改：懒标记（lazy-tag）
【模板】线段树
1
题目描述
已知一个数列，你需要进行下面两种操作：
- 将某区间每一个数加上 \(k\)。
- 求出某区间每一个数的和。
输入格式
第一行包含两个整数 \(n,
m\)，分别表示该数列数字的个数和操作的总个数。
第二行包含 \(n\)
个用空格分隔的整数，其中第 \(i\)
个数字表示数列第 \(i\) 项的初始值。
接下来 \(m\) 行每行包含 \(3\) 或 \(4\) 个整数，表示一个操作，具体如下：
1 x y k：将区间 \([x,
y]\) 内每个数加上 \(k\)。2 x y：输出区间 \([x,
y]\) 内每个数的和。
输出格式
输出包含若干行整数，即为所有操作 2 的结果。
样例输入 #1
1
2
3
4
5
6
7
| 5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
|
样例输出 #1
提示
对于 \(100\%\) 的数据：\(1 \le n, m \le {10}^5\)。
很明显，如果用暴力进行区间修改，不能通过。
那么引入 lazy-tag。
首先，先介绍 lazy-tag 的概念：
对于每个有 lazy-tag
的节点，在只有需要用到自己的子节点时才会把修改的命令（lazy-tag）交给子节点。
lazy-tag 用一个叫做 push_down 的操作下放修改操作。
1
2
3
4
5
6
7
8
9
| void p_d_(long long u)
{
long long L=u<<1,R=u<<1|1;
t[L].sum+=t[u].y*(t[L].r-t[L].l+1);
t[R].sum+=t[u].y*(t[R].r-t[R].l+1);
t[L].y+=t[u].y;
t[R].y+=t[u].y;
t[u].y=0;
}
|
其中，y 就是 lazy-tag。
第二，up_date 函数在符合
t[u].l>=l&&t[u].r<=r 时，将 lazy-tag
加上此次加操作的值，并增加此区间总和。
若不符合，则进行 push_down
操作，为递归左右子树铺垫。
第三，query 函数在
t[u].l>=l&&t[u].r<=r 不成立时，也需进行
push_down 操作，原因同上。
显然，此时复杂度为 \(O(mlogn)\)
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
| #include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y;
long long k;
long long a[500010];
struct tree
{
long long l,r,sum,y;
}t[500010<<2];
void p_u_(long long u)
{
t[u].sum=t[u<<1].sum+t[u<<1|1].sum;
}
void p_d_(long long u)
{
long long L=u<<1,R=u<<1|1;
t[L].sum+=t[u].y*(t[L].r-t[L].l+1);
t[R].sum+=t[u].y*(t[R].r-t[R].l+1);
t[L].y+=t[u].y;
t[R].y+=t[u].y;
t[u].y=0;
}
void b_(long long u,long long l,long long r)
{
t[u].l=l,t[u].r=r;
if(l==r)
{
t[u].sum=a[l];
return;
}
long long mid=l+r>>1;
b_(u<<1,l,mid);
b_(u<<1|1,mid+1,r);
p_u_(u);
}
void u_d_(long long u,long long l,long long r,long long c)
{
if(t[u].l>=l&&t[u].r<=r)
{
t[u].sum+=c*(t[u].r-t[u].l+1);
t[u].y+=c;
return;
}
p_d_(u);
long long mid=(t[u].l+t[u].r)>>1;
if(l<=mid)u_d_(u<<1,x,y,c);
if(r>mid) u_d_(u<<1|1,x,y,c);
p_u_(u);
}
long long q_(long long u,long long l,long long r)
{
if(l<=t[u].l&&r>=t[u].r)return t[u].sum;
p_d_(u);
long long mid=(t[u].l+t[u].r)>>1,ans=0;
if(l<=mid)ans+=q_(u<<1,l,r);
if(r>mid)ans+=q_(u<<1|1,l,r);
return ans;
}
int main()
{
cin>>n>>m;
for(long long i=1;i<=n;i++)
{
cin>>a[i];
}
b_(1,1,n);
while(m--)
{
cin>>k;
if(k==1)
{
cin>>x>>y>>k;
u_d_(1,x,y,k);
}
else
{
cin>>x>>y;
cout<<q_(1,x,y)<<endl;
}
}
return 0;
}
|
权值线段树
普通的线段树，记录的是数组中当前区间的各种信息。
权值线段树，则记录的是每种数据出现的次数。
如：数组为 1 1 4 5 1 4
则其出现次数为（从 \(0\)
开始）0 3 0 0 2 1。
线段树合并
前置知识：权值线段树（一般线段树合并合并的是权值线段树）。
线段树合并是指建立一棵新的线段树，这棵线段树的每个节点都是两棵原线段树对应节点合并后的结果。它常常被用于维护树上或是图上的信息。——OI
wiki
如果每次合并都新开一棵满树，时间、空间都无法接受。
那么，就需要本文开头提到的前置知识动态开点。
设需要合并的两棵树分别叫 \(T1\) 和
\(T2\)。
从上往下（即从 \(1\)
号节点开始递归向下），对于每个节点，若 \(T1\) 上无此节点，就只加入 \(T2\) 上的此节点。反之亦然。
如果都有此节点，若是叶子节点，直接合并所有信息。
若否，通过子节点的返回（返回左儿子、右儿子）更新。
OI-wiki
上对其时间复杂度的证明不严谨，读者可以在写的时候自己证其时间复杂度。
扫描线
下面这张动图，诠释了这种算法在处理面积并上的的大致思路：（感谢
OI-wiki，面积并处理部分也请参见 OI-wiki）
本博客则讲述其解决周长并上的解法，详见T7。
例题
T1
首先的思路是暴力（二维前缀和），然而会时间和空间超限。
优化：因为“星星按y坐标增序给出，y坐标相同的按x坐标增序给出”，所以只需查找从
\(0\)
高度到此高度范围内共有多少颗星星（因为保证 \(y\) 增序了），求和即可。
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
121
122
123
124
125
126
127
| #include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
i128 f=1;
x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
void writing(i128 x)
{
if(x>=10)writing(x/10);
putchar(x%10+'0');
}
void write(i128 x)
{
if(x<0)
{
cout<<'-';
x=-x;
}
writing(x);
}
LL n,x[1000010],y[1000010];
LL k;
LL a[1000010];
struct tree
{
LL l,r,sum,y;
}t[1000010<<2];
void p_u_(LL u)
{
t[u].sum=t[u<<1].sum+t[u<<1|1].sum;
}
void p_d_(LL u)
{
LL L=u<<1,R=u<<1|1;
t[L].sum+=t[u].y*(t[L].r-t[L].l+1);
t[R].sum+=t[u].y*(t[R].r-t[R].l+1);
t[L].y+=t[u].y;
t[R].y+=t[u].y;
t[u].y=0;
}
void b_(LL u,LL l,LL r)
{
t[u].l=l;
t[u].r=r;
if(l==r)
{
return;
}
LL mid=l+r>>1;
b_(u<<1,l,mid);
b_(u<<1|1,mid+1,r);
p_u_(u);
}
void u_d_(LL u,LL l,LL r,LL c)
{
if(t[u].l>=l&&t[u].r<=r)
{
t[u].sum+=c*(t[u].r-t[u].l+1);
t[u].y+=c;
return;
}
p_d_(u);
LL mid=(t[u].l+t[u].r)>>1;
if(l<=mid)u_d_(u<<1,l,r,c);
if(r>mid) u_d_(u<<1|1,l,r,c);
p_u_(u);
}
LL q_(LL u,LL l,LL r)
{
if(l<=t[u].l&&r>=t[u].r)return t[u].sum;
p_d_(u);
LL mid=(t[u].l+t[u].r)>>1,ans=0;
if(l<=mid)ans+=q_(u<<1,l,r);
if(r>mid)ans+=q_(u<<1|1,l,r);
return ans;
}
LL sum[1000010];
int main()
{
cin>>n;
b_(1,1,320000);
rep(i,1,n,1)
{
cin>>x[i]>>y[i];
}
rep(i,1,n,1)
{
LL u=x[i]+1;
LL v=q_(1,1,u);
u_d_(1,u,u,1);
sum[v+1]++;
}
rep(i,1,n,1)
{
cout<<sum[i]<<endl;
}
return 0;
}
|
很明显，因为是“区查单改”且是较为特殊的异或，我们需要把“异或次数”作为
lazy-tag。
同时因为只有 \(1\) 和 \(0\)，所以 lazy-tag 每次异或（即 \(+1\bmod 2\)）即可。
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
121
122
123
124
125
126
127
| #include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 LL
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
i128 f=1;
x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
void writing(i128 x)
{
if(x>=10)writing(x/10);
putchar(x%10+'0');
}
void write(i128 x)
{
if(x<0)
{
cout<<'-';
x=-x;
}
writing(x);
}
LL n,m,x,y,k,a[100010],tt[100010];
struct tree
{
LL l,r,sum,y;
}t[100010<<2];
void p_u_(LL u)
{
t[u].sum=t[u<<1].sum+t[u<<1|1].sum;
}
void p_d_(LL u)
{
LL L=u<<1,R=u<<1|1;
t[L].sum=t[L].r-t[L].l+1-t[L].sum;
t[R].sum=t[R].r-t[R].l+1-t[R].sum;
t[L].y^=1;
t[R].y^=1;
t[u].y=0;
}
void b_(LL u,LL l,LL r)
{
t[u].l=l,t[u].r=r;
if(l==r)
{
t[u].sum=tt[l-1];
return;
}
LL mid=(l+r)>>1;
b_(u<<1,l,mid);
b_(u<<1|1,mid+1,r);
p_u_(u);
}
void u_d_(LL u,LL l,LL r)
{
if(t[u].l>=l&&t[u].r<=r)
{
t[u].sum=t[u].r-t[u].l+1-t[u].sum;
t[u].y^=1;
return;
}
if(t[u].y)p_d_(u);
LL mid=(t[u].l+t[u].r)>>1;
if(l<=mid)u_d_(u<<1,l,r);
if(r>mid)u_d_(u<<1|1,l,r);
p_u_(u);
}
LL q_(LL u,LL l,LL r)
{
if(l<=t[u].l&&r>=t[u].r)return t[u].sum;
if(t[u].y)p_d_(u);
LL mid=(t[u].l+t[u].r)>>1,ans=0;
if(l<=mid)ans+=q_(u<<1,l,r);
if(r>mid)ans+=q_(u<<1|1,l,r);
return ans;
}
int main()
{
read(n);
read(m);
b_(1,1,n);
while(m--)
{
read(k);
if(k==1)
{
read(x);
read(y);
u_d_(1,x,y);
}
else
{
read(x);
y=x;
write(q_(1,x,y));
puts("");
}
}
return 0;
}
|
当然，“开方”操作的懒标记以及修改都很难做。
然而，我们发现：\(\Bigg \lfloor
\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt 10^{12}}}}}} \Bigg
\rfloor=1\)
所以就这样操作即可：不是全 \(0\)
或全 \(1\)，暴力；是，不管。
我们需要两个 lazy-tag，一个是乘的，一个是加的。
优先级是乘 \(>\)
加，因为加完再乘，加的那部分也要被乘，反之不然。
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
| #include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int n,m,p,opt,x,y,k;
int a[N];
struct xds
{
int l,r,sum,m,a;
}t[N<<2];
void pu(int u)
{
t[u].sum=(t[u<<1].sum+t[u<<1|1].sum)%p;
}
void pd(int u)
{
int l=u<<1,r=l|1;
t[l].sum=(1ll*t[l].sum*t[u].m+1ll*(t[l].r-t[l].l+1)*t[u].a)%p;
t[r].sum=(1ll*t[r].sum*t[u].m+1ll*(t[r].r-t[r].l+1)*t[u].a)%p;
t[l].m=1ll*t[l].m*t[u].m%p;
t[r].m=1ll*t[r].m*t[u].m%p;
t[l].a=(1ll*t[l].a*t[u].m+t[u].a)%p;
t[r].a=(1ll*t[r].a*t[u].m+t[u].a)%p;
t[u].m=1;
t[u].a=0;
}
void b(int u,int l,int r)
{
t[u].l=l;
t[u].r=r;
t[u].m=1;
if(l==r)
{
t[u].sum=a[l];
return;
}
int z=t[u].l+t[u].r>>1;
b(u<<1,l,z);
b(u<<1|1,z+1,r);
pu(u);
}
void mu(int u,int l,int r,int k)
{
if(t[u].l>=l&&t[u].r<=r)
{
t[u].sum=1ll*t[u].sum*k%p;
t[u].m=1ll*t[u].m*k%p;
t[u].a=1ll*t[u].a*k%p;
return;
}
if(t[u].m!=1||t[u].a)pd(u);
int z=t[u].l+t[u].r>>1;
if(l<=z)mu(u<<1,l,r,k);
if(r>z)mu(u<<1|1,l,r,k);
pu(u);
}
void au(int u,int l,int r,int k)
{
if(t[u].l>=l&&t[u].r<=r)
{
t[u].sum=(t[u].sum+1ll*k*(t[u].r-t[u].l+1))%p;
t[u].a=(t[u].a+k)%p;
return;
}
if(t[u].m!=1||t[u].a)pd(u);
int z=t[u].l+t[u].r>>1;
if(l<=z)au(u<<1,l,r,k);
if(r>z)au(u<<1|1,l,r,k);
pu(u);
}
int q(int u,int l,int r)
{
if(t[u].l>=l&&t[u].r<=r)return t[u].sum;
if(t[u].m!=1||t[u].a)pd(u);
int z=t[u].l+t[u].r>>1,sum=0;
if(l<=z)sum=(sum+q(u<<1,l,r))%p;
if(r>z) sum=(sum+q(u<<1|1,l,r))%p;
return sum;
}
int main()
{
cin>>n>>m>>p;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
b(1,1,n);
while(m--)
{
cin>>opt;
if(opt==1)
{
cin>>x>>y>>k;
mu(1,x,y,k);
}
if(opt==2)
{
cin>>x>>y>>k;
au(1,x,y,k);
}
if(opt==3)
{
cin>>x>>y;
cout<<q(1,x,y)<<endl;
}
}
return 0;
}
|
T5
工厂
小明的叔叔是一家工厂的厂长。叔叔的工厂有 n 个车间，编号为 1～n。
管理工厂是很麻烦的事情，特别是在多次调整机器以及员工之后，统计总生产量更是难事。
第 i 个车间在刚开始的时候机器生产力为 ai，有 bi
个员工，那么这个车间的生产力就为ai*bi。
工厂的总生产力定义为所有车间的生产力之和。
接下来的 m 天，每天叔叔就会调整一段区间的车间。
有两种调整：
第一种，是对于一段区间[l,r]的每一个车间重新分配每个车间的工人数为
x。
第二种，是对于一段区间[l,r]的每一个车间增加机器生产力 x。
现在，小明的叔叔想知道每天调整之后工厂的生产量变为多少。
我们发现，这和 T4 很像，只是“加”变为了“覆盖”。
于是把“加” lazy-tag 变为“覆盖”的即可。
code(thanks to lqs)
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
| #include<stdio.h>
#include<bits/stdc++.h>
#define N 400010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define ls (x<<1)
#define rs (ls+1)
#define lm (l+r>>1)
#define rm (lm+1)
using namespace std;
void read(i128 &x)
{
i128 f=1;
x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
void writing(i128 x)
{
if(x>=10)writing(x/10);
putchar(x%10+'0');
}
void write(i128 x)
{
if(x<0)
{
cout<<'-';
x=-x;
}
writing(x);
}
LL n,q,s,t,d,a[N],b[N],ans[N],sa[N],sb[N],ta[N],tb[N];
string op;
void pu(LL x)
{
ans[x]=ans[ls]+ans[rs];
sa[x]=sa[ls]+sa[rs];
sb[x]=sb[ls]+sb[rs];
}
void pd(LL x,LL l,LL r)
{
sa[ls]+=ta[x]*(lm-l+1);
sa[rs]+=ta[x]*(r-rm+1);
ta[ls]+=ta[x];
ta[rs]+=ta[x];
if(tb[x])
{
sb[ls]=tb[x]*(lm-l+1);
sb[rs]=tb[x]*(r-rm+1);
ans[ls]=tb[x]*sa[ls];
ans[rs]=tb[x]*sa[rs];
tb[ls]=tb[rs]=tb[x];
tb[x]=0;
}
else
{
ans[ls]+=ta[x]*sb[ls];
ans[rs]+=ta[x]*sb[rs];
}
ta[x]=0;
}
void bu(LL x,LL l,LL r)
{
if(l==r)
{
ans[x]=a[l]*b[l];
sa[x]=a[l];
sb[x]=b[l];
return;
}
bu(ls,l,lm);
bu(rs,rm,r);
pu(x);
}
void se(LL x,LL l,LL r)
{
if(t<l||s>r)return;
if(s<=l&&r<=t)
{
sb[x]=d*(r-l+1);
ans[x]=d*sa[x];
tb[x]=d;
return;
}
pd(x,l,r);
se(ls,l,lm);
se(rs,rm,r);
pu(x);
}
void add(LL x,LL l,LL r)
{
if(t<l||s>r)return;
if(s<=l&&r<=t)
{
sa[x]+=d*(r-l+1);
ans[x]+=d*sb[x];
ta[x]+=d;
return;
}
pd(x,l,r);
add(ls,l,lm);
add(rs,rm,r);
pu(x);
}
int main()
{
cin>>n>>q;
rep(i,1,n,1)cin>>a[i]>>b[i];
bu(1,1,n);
while(q--)
{
cin>>op>>s>>t>>d;
if(op=="Set")
{
se(1,1,n);
}
else
{
add(1,1,n);
}
cout<<ans[1]<<endl;
}
return 0;
}
|
权值线段树 \(+\) 线段树合并。
每个子树中的颜色，开一颗权值线段树，向上回溯时合并即可。
首先，需要离散化，而后处理时有两种思路：
用一棵线段树，所以有一点点思维难度。
从上向下扫描，每次遇到一条边，若为上边，则在线段树上此区间进行加操作，下边则在此区间进行减操作。与面积并时相似。这是横边。竖边则利用扫描线走过的距离乘横向距离即可。
可以参考这篇题解。
思路一的思维难度在于，竖边的处理较为麻烦，那么我们就如法炮制，竖边也建一棵线段树处理。
小结
其实线段树还有不少应用，限于篇幅只能列出一部分。
赛中一般不会出裸线段树，所以想到用线段树是一个重要环节。
剩余部分可以参见
OI-wiki，讲的很清晰。有时间或有需求也可以学习几种线段树变形（李超等）。
另，由于部分题目代码过于长或因为某题最好自己写代码以学习，所以我没有放。
致谢
我学校的信息学教练 zxc 以及不是我学校的一位教练
gtc，为此文提供了例题以及基础；
OI-wiki 线段树部分编写人员及 OI-wiki
建设者，为本文线段树合并部分提供了定义以及为扫描线提供动图讲解；
我之前的英语老师 Cally，为本博客风格提供建议；
同学 lqs、whl，为我改代码（T5，lqs），讲解 T4（whl）；
hexo、github以及 next，为本博客提供支持；
同学 lyh，帮我调弄 hexo；
洛谷，提供题目、上传图片、教会我 \(\LaTeX\)；
\(mathjax\)，对本文提供 \(\LaTeX\) 支持。